I don't know if Paint has improved, but what I recall it always used to distort any images imported.. like you can tell the quality suffer after a few generation exports of the image.
Most graphix members here use Adobe Photoshop. I know it's a very steep learning curve on using it, but with the assistance of online tutorials (esp. youtube.com) you can probably get by with a few here and there.
I am just curious as to why you are asking this in the Homebrew Discussion section? Is this a new PSP feauture I don't know about? You know this place has it's own Graphix section esp. here:
http://pspbrew.com/forum/viewforum.php?f=43 (Graphix Tutorial Collection).