256 colors, palette
Red = 255
Green = 0
Blue = 255
Also, you can just use the eye-dropper to get the correct color.
Unless Rufus erred in the actual creation, it's likely you altered something - maybe shrunk/enlarged the image? What ends up happening in those cases is that the image stretches/compacts and thus the image blends with the surrounding pink. The bordering pixels may then become a color somewhere between the 2 adjacent colors, thus producing an off-pink image that doesn't become transparent in game.
If you were altering the image size, here's a correct way to do so:
Copy the image onto a new canvas where the background is transparent. Remove all the pink, so you only have the actual image left. Make your size adjustments, then copy the image and place it back on the proper pink background.
EDIT: and yes Photoshop works, I believe Paintshop is fine as well. You essentially are looking for anything that can handle a pcx image.