Here are the guidelines:
85X85 pixel size
7.5 KB file size
gif/jpg file type

If it's jpg or .gif, you've got it down to 60x40 pixels, and it still won't work, then the file size is too big.

(jkevans' avatar is actually 80x60 pixels, at 1.47KB, for instance.)