I think I know what you mean. This can happen if you change the file extension while saving and reduce the quality at the same time. Or not reducing the quality but saving in GIF.
So, how did you saved the file?
Another thing I need to say. If you go back and forth from a file extension to another (well actually it depend on the extension used), it mean that every time you do it the picture lose some of its quality. For example, I know a professional photographer that always modified his file in Photoshop and then compressed everything in a jpeg with no back up. And he could do this a couple of time with the same file. It does a very bad job.
To conclude, my advice is : if you can manage to use Gimp, you should stop using MSpaint since Gimp offers way more possibilities.