The size of the file refers to the pixel dimensions. Simply use Image > Resize > Image Size to reduct the pixel dimentions that your are using. Likely cutting the size in half will allow things to work.
Actually, you can almost always safely ignore this. S4W is just older technology and with many modern cameras with higher megapixel counts it pops up this warning. If you try one and it doesn't freeze/crash PSE, then you can ignore it in the future. If you proceed and do have trouble, then try Brett N's suggestion.
I am trying to make an animated pixel figure. I have set up transparent pixels, though to make the background, and when its animated, you can see the previous frame behind the original. Is there any way to help this? The first three frames don't appear to have this problem, but after that this happens.
Basically, how animation works with GIF and Save for Web in PSE is that each layer in your document is a frame of animation. So you see one layer, then the next, and so on. You should not see the contents of the last frame/layer when looking at the current/next frame of the animation.
Could you post a screen shot of your layers panel and give us a link to the GIF that is coming out of Save for Web?