#1 - Are you sure the exact dimensions are 50 x 50 pixels? If it's anything less or anything more it's not going to work. Since you are using photoshop.. go to image, then image size, and set it to 50 x 50 (pixels) to ensure this.
#2 - Are you saving it as a gif or jpg? It doesn't seem to like too many other formats. So stick to those.
#3 - How close are you to the file size limit? If you are saving it and it's coming out around 7.6k or 7.4k .. etc you might actually be going over the 8k limit without realizing it. Files sometimes take up extra physical memory and/or file size reading isn't always exact (decimal/binary = 1024 not 1000) so it can throw things off sometimes.
To ensure this isn't happening - When you save it.. Go to File, Save For Web & Devices, and choose GIF format and drop the amount of colors it's using.
Unless you are trying to do an animated icon there is NO reason why you shouldn't be able to compress it to under 2k and still look sexy.
If it's still not working for you.. Why not just download the ready to go set of icons I uploaded on here the other day. There's something like 1700+ icons designed for ns.. so you should be able to find something in there.