You could be having a problem in that Not All Reds Are Created Equal. The unit uses red (RGB values FF/00/00) as the mask color, but a program like Paintshop is going to treat red as... a color. Perhaps it's trying to be "helpful", and blend the red into the background around the edges? That would result in a .bmp where the color on the edges isn't exactly red, maybe something like F0/00/00. It'll look just as red as can be to you, but the unit will see it as not-red and it'll be displayed instead of made transparent.
My son made me a car symbol, depicting GIR, the sweet killer robot from Invader Zim. He worked from a full-size image, carefully matted the outside with red... and then reduced the image. The (Linux) paint program he used, though, "helpfully" mixed the red close to the character's edge with the nearby pixels, for anti-aliasing. As a result, GIR has a bit of a red edge to him, because the colors aren't pure FF/00/00. I wouldn't be surprised if that's the problem you're having.
Here's a hint that finds those not-quite-red red pixels. Pick some color that you don't have in your image, and flood-fill the red with it. If that border on the outside remains, then it wasn't the same FF/00/00 as the rest.
Your best bet is to use the most brain-dead, simple graphic editor possible for the final .bmp. Windows Paint is pretty much ideal... it's as brain-dead as they come.