I've done the requisite post search and didn't find my exact issue.
My buddy icons change but don't update for everyone. Some folks can see my new icons, others cant. I trashed prefs as per your site and my global icon has changed but doesn't change my local icons, especially for aim.
You might want to check your settings for the individual services. If you go into preferences >accounts and edit the account, there is a tab for Personal. There you can specify whether to use the global icon or a different one only for that service such as aim.
It is possible you have an icon set to override the global.
Hope this helps.
Dr Q
iMac & MacBook Pro, OS 10.6.7, Portable Adium using AdiumX 1.4.1