I have to disagree; when you're as keyboard oriented as I am, having a resource-light program like Paint with simple keyboard shortcuts works wonder for most maps.
I do use other tools for specific functions like removing specific colors in large quantity, transparencies, etc, but I always complete things in Paint. Now that I actually have a computer capable of running a more sophisticated program, I could try one, but I don't know which would be good enough for me, and I'm not willing to spend a couple hundred dollars only to go back to using Paint at the end.
There's Photoshop obviously, which might work if a budget version without the more advanced and professional filter functions exists. I've used Paint Shop Pro in the past, and it wasn't bad, but doing the same thing as in Paint took twice as long and more mouse and keyboard manipulations.
It all comes down to keyboard shortcuts and simplicity to me. When I paste something, I expect the selected background color to disappear and the pasted area to appear at the top-left corner of the visible canvas. When I select an area and press DEL, I expect it to be replaced by the background color. That sort of thing.
To me, using Paint is like using a simple 5$ metal corkscrew to open a bottle rather than the aluminum-cast electric corkscrew that plays music and cost you 150$. Personal opinion of course
---
Current projects: Ristar-The Shooting Star (Gen), Sonic The Hedgehog (Gen), Sonic CD (Sega CD), Mega Man Zero (GBA), Battletoads (NES), Bucky O'Hare (NES)