As seems the problem was related to SELinux Policy corruption. It also affected cron and other services, but I'm not sure if this was directly related. Not sure how the corruption occured, maybe some hardware failure or something after power failure...
Anyway reinstalling SELinux Policy solved all this things.