Why does the "password" prompt take forever when I SSH into my Ubuntu 9.05 server?

Is it possible it's doing a reverse DNS lookup on your IP? You can check the results online if the client is using a public IP address, or use something like the following from your server:

dig -x CLIENT_IP_ADDRESS

Is there anything in /var/log/messages?

Probably the reverse DNS resolution (server trying to get client's name given IP) is taking time. Can you check if /etc/ssh/sshd_config has setting "VerifyReverseMapping yes" ? Set it to "VerifyReverseMapping no" and check if helps.

Edit: It seems VerifyReverseMapping is now deprecated and useDNS is the new configuration in the sshd_config.