I had similar problems when making album art for my mp3s on the Clip Zip. I found that if I follow three rules problem solved.
1: I make sure that the picture is square (which it sounds like you are doing)
2: I like to use JPEG (though I’ve noticed other formates seem to work fine as well, but I just like to keep a standard)
3: The file has to be under 20kb, which it looks like you are a bit over. Even if the pictures are all the same “size” (480x480 in your case), if you have a higher resolution it may get over that 20kb threshold, and therefore won’t show up.
This works for my Zip, and so far seems ok with my Sport too, but I’ve not played with it as much. May be a good place to start though.