first off, make sure the icon is the proper size in dimensions (50x50 pixels). To do this, go to Image > Image Size > Width: 50 Height: 50 pixels (on the right, make sure it's not PERCENT)
Now, let's take the file size down.
You want to save your icon as a .gif file, since gif's are based off simple colors. In the bottom corner, it'll tell you how big your file currently is (for example, 2.17K). For Ns, you are going to want your icon to be under 1.94k.
1.94k is about equal to 1997 bytes. 1.95k is more than the site's limit on icon size (2,000 bytes).
So, to chop the file size down Go to the 'color' option on the right. Tamper with it Up/Down until it's at a desirable file size. Usually 64 colors works fine.
Eat. Sleep. Breathe. Ski.