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.