I am experiencing what I think is the same problem in 10.04. It wasn't a problem in any of the versions prior to this on the one machine, but an upgrade recently caused this to affect ~50% of cold boots.
It's not difficult to solve - once the failed login happens (home is not mapped), I go to one of the terminals (crtl-alt-F1), and issue:
sudo /etc/init.d/autofs reload
After this, I can switch back to the KDE/Gnome prompt and login through the graphical prompt, which is now crtl-alt-F8.