Only use MS Paint if you intend to do any custom sprite tweaking for cover screenshots. That's pretty much all it's good for.
I use GIMP. GIMP is pretty good at making covers. However, keep in mind that GIMP processes certain Photoshop layers differently, making working with most of the Cover Templates a tricky deal. GIMP can't edit the text layers in the PSD files, and you'll have to re-do those. Also, some gradient layers will not show up at all, meaning you'll have to re-build some aspects on your own.