I had that same message about a year ago, after changing my hard drive (I'm using XP by the way). But it was my copy of Painter X, not IX.5 (which I also have, but worked fine and wasn't affected).

Same as you, no amount of uninstalling and reinstalling did anything to fix the problem. After long sessions of searching the net, I found some advice HERE (see bottom of the page).

Which was basically search for and delete all registry entries called "Protexis" (I think I found 2 entries), being carefully not to touch anything else by mistake and so wreak your registry. (back up your registry before hand just in case)

There is the second option on that page, but frankly I didn't know what that was on about and since the first fix worked, I went no further.

I hope this works as well for you as it did for me.