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.