Why does lastlog show every user as never having logged in?

Login via gdm is not logged in lastlog. In this respect ck-history --last might give you more information.

To test this, go to a console (Ctrl+Alt+F1), log in, then come back to Gnome (Alt+F7) and check the output of lastlog.

Can you post the output of lastlog? Are you sure they all say never logged in? Mine shows that only two accounts have logged in (root, and my own user account). The rest are a bunch of system accounts like pulse, avahi, sshd which have never actually had a log in. Also, /var/log/lastlog shouldn't be empty, but it is (according to less) a binary file that requires the lastlog program to parse.

Maybe you are affected by this expired bug?