In short, Facebook is converting your image to the JPEG/JPG format (Join Photographic Experts Group). There seems to be no current way to upload images to use as a profile picture or to your photo album which Facebook will not convert to JPEG.
...a commonly used method of lossy compression for digital photography
(image). The degree of compression can be adjusted, allowing a
selectable tradeoff between storage size and image quality
other hand, JPEG may not be as well suited for line drawings and other
textual or iconic graphics, where the sharp contrasts between adjacent
pixels can cause noticeable artifacts. Such images may be better saved
in a lossless graphics format such as TIFF, GIF, PNG, or a raw image
JPEG is not suitable for images with text, large blocks of color, or
simple shapes, because crisp lines will blur and colors can shift.
The above quote “JPEG is not suitable for images ... large blocks of color” pinpoints your issue. In a photograph, colors tend to have some variation and/or shading. JPEG introduces what has been called, ‘noise’, ‘artifacts’, 'mottling', etcetera.
Tip for saving JPEG Images: As JPEG is a lossy image format, try to preserve as much of the data of these type of images as possible. When saving an image with blocks of color in the JPEG format, your software should give you an option for image quality. This is usually a slider you set to 100 to save the maximum data quality.
Tip for uploading JPEG images: When uploading to Facebook, check the radio button: “High Resolution(takes ~10x longer)”.
Easiest solution (convert the block color): Try converting the image to solid black. This usually lessens the mottling effect (though doesn’t totally eliminate). Certain colors tend to show the mottling effect, instead of black you could try other colors and see if the mottling effect is less noticeable.
More advanced solution 1 (introduce texture via noise to the solid color): The problem is that JPEG doesn’t deal with solid colors well. A solution would be to make the color less solid. One standard way to doing so is to use the noise filter in your image editing program. Noise can introduce new jarring colors. Because of this, noise filters often have a way of protecting hue, or one can turn down ‘color saturation’, or some such. This step in a Photoshop tutorial shows the Add Noise Dialog, which uses a Monochromatic setting to preserve hue. I personally tend towards Gaussian, but try both settings to see which yields better results.
More advanced solution 2 (introduce texture to the solid color): Most image editing programs have filters which can alter images. Some ‘artistic’ filters do this. The goal here is to break up solid colors so that the imperfections of JPEG are not noticeable or displeasing.