If you have PSP, then you've got everything you need for pixel art. It's superior to paint in that it can scan images, replace colour (I use that ALL the time), use multiple layers (another must-have for any serious pixel artist who does animation. It's possible without it, but layers make it SO much quicker). You can zoom in between a pretty huge ratio (that's a lot of zooms -- better than Paint's 2x, 4x, 6x and 8x zooms). You can use a visible grid, guides on the ruler, snap-to functions, and rather than just having a simple 'select all of one colour' function, you can also choose colour tolerance, allowing you to select all pixels close to a certain colour. Great if you work with a lot of dithered images.
I've not opened paint once since I got PSP, there's simply no need to. If you PM me, I'll send you my MSN email address, and I can tell you more about using PSP for pixel art via MSN Messenger.
Oh, and replacing single colours in the pallette (if you choose to use a pallette) is a feature I use a lot too. For those times when Replace Colour is being a pain.