You have a @googlemail account and each time you try to connect with Gaim it gives you an "Authentication failure"?
Right, instead of entering server=gmail.com as specified in the instructions, enter server=googlemail.com
It's as simple as that ... I already tried installing TLS packages and all sorts of weird suggestions on forums, until I found this subtle detail.
Obviously this will just apply to those people in countries where Google had legal issues with gmail's name and had to rename it as "google mail". For example, UK.