AIM has a tendency to allow old passwords to be used for a while. I've noticed that friends accounts allow me to logon with month old passwords. This goes for checking their e-mail as well. (They gave me permission.)

Try logging on with all of the old passwords if resetting it doesn't work. AIM may have changed this in the last few years, but AOL has never been that great about updating their databases, so the clearing out of old passwords (originally meant as a nice thing for the forgetful folk) may still be there.

Hope this helps.