FWIW, I just found this thread on a search and wanted to say I'm having the same issue.

Attempting to log in to my Ubuntu 9.04 Server box from a 9.10 Desktop installation. I can't log in unless I've actually logged in on the server first. If it's on the login screen, I get the Permission denied (publickey).