I tried downloading a trial version of PSP5, and that worked, but it didn't really do me any good since it only worked for 30 days.

So I tried some of the steps in these instructions for uninstalling PSP8. I also found some other things titled, "paint shop pro" in the registry, and I deleted those too. Tried installing PSP5 again, still didn't work. Tried restarting in safe mode, and installing from the splash screen. Still didn't work. Then, while still in safemode, I went into the install folder of the PSP5 CD ran the Setup.exe file. That worked. I restarted back in normal mode and it still seems to be working.