I've noticed that changing file format often generates a lot of stray pixels at the color transitions. I've been using PSP 7 more recently for transparency. If the background (and it's associated strays) is different enough from any of the other colors in the image, I've found that the "tolerance" that you can set for color match really comes in handy.