I have always been a Paint Shop Pro user. I have tried Photoshop from time to time and have found it very slow to use - in Paint Shop Pro, saving GIF files much easier because the menus to make the color changes are very easy to quickly reach. What I like most about Paint Shop Pro is it's simplicity. As there are many more options in Photoshop, I found it tended to slow work down. Speed is an issue to me, because when trying to save all the small images to make up a menu on a website I want to be able to cut up the parts as fast as possible.
This probably only applies to older versions of Photoshop. I haven't tried it for a few years, so these things might have improved.
As soon as Paint Shop Pro 7 was released I downloaded the demo version at once, and found I wasn't really happy with it. It had started to include some of the the ideas I didn't like about Photoshop. For example, in Paint Shop Pro 6 there are one set of colors you can use for everything. However in version seven, you have a different palette for each tool (i.e. text, drawing, flood fill etc.) This really slowed me down, because I like to work with a certain set of colors, rather than switching to a different tool and finding I didn't have the color anymore.
Therefore, I still use Paint Shop Pro 6 - and I'm happy with it!
So try out both programs and see what you like the most. I think though that Paint Shop Pro 7 is no better than Photoshop - I'll probably switch to it eventually.