This morning, AIM proposed me an upgrade. Well, ok, let's do it. I can immediately see the difference!!! I was trying to send a message to Chris Hofmann and here's the great, marvelous, so typical of AOL, result:

AIM error message, your buddy can't receive IM

Update: leaving and restarting AIM fixed the problem. Weird, very weird.