it's got to do with the way you save them. Make sure you don't over-optimise them.... And make sure that you're in the right colour space. ugh... i forget what it's called it's been ages since I opened PS! (yes I know blasphemous!) Anyway, I had the same problem sort of too... a while ago. This thread might help you: http://www.thephotoforum.com/forum/showthread.php?t=30592&highlight=colour
Make sure your avatar is exactly 100x100 pixels and is less than 23Kb in size. Or... send it to me and I'll PS it for you! Rob