I've installed Ubuntu 11.10 on my two System76 laptops (I have a Lemur and a Serval), and on both machines I noticed while I was configuring Empathy it wouldn't log into AOL IM successfully.

After verifying I wasn't fat-fingering my password I did some poking around and came across a post-install to-do list for Ubuntu 11.10 that fixed the issue for me. You can of course pick and choose which plugins to install, but I suspect just using the latest version did the trick. There were some on-again off-again bugs related to AIM and ICQ logins during 11.10 development.

Full details are in the linked blog post above, but here's the basics:

sudo add-apt-repository ppa:telepathy/ppa
sudo apt-get update && sudo apt-get upgrade
sudo apt-get install empathy

With the new version the AIM login issue immediately went away.