Is it 75x75 or less?
That's only for .gifs, if it's larger than 75x75 it resizes it to fit, that's what breaks them, normal images are fine though. It's usually better to resize normal images to fit so you don't lose quality.
When I change my avatar i have to hit ctrl+f5 a couple times before I can see the result.