Welcome to LQ!
Login as root and check the permissions on /home/ with
stat --printf "a %n \n" /home/*
and post the results here.
Erm, that may not "help" since new users have the same issue...
Curious, but I don't have an immediate clue, or answer.
Does /var/log/secure show anything obvious?
Can users login from the console?