I just installed gaim last night, and had a similar issue.
From my Linux notes:
>apt-get install gaim
error: failed to fetch gaim from freshrpms
notice: gonna install gtkspell
>apt-get install gtkspell
go to www.aim.com
and download AIM for Linux 1.5.286
>rpm -Uvh aim-1.5*
I guess freshrpms didn't have a version of gaim to install. I just got the rpm from www.aim.com,
downloaded it, and installed it with rpm.