Are you taking an image and shrinking it down? What are you using? Preview has an option to target a file size. Otherwise, try ImageJ or GIMP and once you save a picture in avatar size as a JPG you shouldn't have too many problems.
I just used ImageJ to size my Avatar for here (since I just earned it last night )