I have just managed to change my avatar and only because I had resized it first.
If your picture is more than approx 85x 85 it wont upload. You can edit and re-size it by left clicking the picture and resizing to within the pixel limit.
Unfortunately if you have an animated or glittering avatar, re-sizing will delete the movement and you will be left with a plain picture. (as you can see)
Hope that helps,