One of the built-in pieces of security in many linux machines is a piece of software called denyhosts. This piece of software works with the SSH daemon to catalog the types of requests and failures come in. If it detects an IP trying to connect to the computer that has exceeded certain thresholds, it adds it tot he /etc/hosts.deny file, which immediately bans an IP from connecting with ssh.
In the default settings in Ubuntu, valid users are only allowed 10 failed valid-username attempts over a period of 5 days, or 5 failed invalid-usernames over the same period.. This may seem like plenty, but occasionally when travelling you will repeatedly use the wrong password or the wrong username, you can get your entire IP blocked. At this point you have to use another machine (or another IP) to connect to the server to fix the problem.
How to unban yourself in DenyHosts
The easiest way to temporarily unban yourself is to delete the entry containing your IP in /etc/hosts.deny. This will work for a few seconds, before DenyHosts regenerates the file. It should be enough to connect and fix the issue from your main host. You will also want to do this in combination with the next step.
How to fix the problem permanently
In my opinion, the problem with DenyHosts in a default Ubuntu install is that successful connections don't reset any of the failure counts. This means that if you attempt to connect each day, and fail twice, and succeed on the third attempt, by the 3rd day of this, you could be banned from your own server.
The fix involves editing your /etc/denyhosts.conf. Open this file as root in your preferred editor, and locate the configuration option RESET_ON_SUCCESS and make the line read as follows:
After making this change, and restarting denyhosts with /etc/init.d/denyhosts restart, you will want to unban your IP, and connect again successfully so that your fail counts are reset. Hopefully from there, you won't be banned by your own innocent login failures.