Try reducing the size of the photos to at least 1600 x 1600 pixels. Most 4 megapixels camera phones these days will be 2240x1680.
Just use Windows Picture Manager program to reduce the size of your photos.

Profile pics have a maximum size of 200 x 200 pixels with a maximum size of 600kb.