You answered your own question there, I believe. Don't use Paint.
More specifically: if you try to save an image in a format that isn't 24-bit or higher, then MS Paint will use its default and incomplete palette for it, and do very, very bad dithering. Saving anything in such a format will nearly guarantee that it will look very bad - discolored, as you say.
Furthermore, some versions of Paint will apparently reduce the brightness of an image a little every time they save it. Sounds nasty to me.
In any case, you should save the screenshot as a PNG. It will give it a small filesize and not suffer the horrible abominations that are color reduction and JPEG compression - two things that, I should add, Paint does a very, very bad job of.