Surprisingly, I did and I hope it'll help you.
Basically, Nokia PC Suite Cleaner is a piece of **bleep**. It doesn't erase everything from your computer thus you can't reinstall.
What I did is run the cleaner first - because it erases at least something. Notice that if you still have a problem, after you've runt he cleaner, it says that the product can't be uninstalled because there was no valid installation source and that the registry has been cleaned. This is a sign that you still have a problem and won't be able to install the NPS. Then you have to search your entire hard drive where Nokia PC Suite was installed for "nokia", including hidden and system files.
One of the paths you'll find is this:
C:\Documents and Settings\Jonathan\Application Data\Nokia
Back everything up from this folder and then delete it. Your settings and backups are stored there, but apparently if you don't remove it you won't get anywhere.
Then you have to do some registry cleaning. I used the CCleaner (
http://www.ccleaner.com/) and then Eusing Free Registry Cleaner (
http://www.eusing.com/free_registry_cleaner/registry_cleaner.htm). With each software you have to run the cleaning several times at a time - for example, run the CCleaner once, let it back up your registry, repair all the issues, then run again. I did it until in both programs nothing was showing up anymore.
After that, I've restarted the computer and ran the Nokia PC Suite Cleaner again. This time, it said that no products were found. That's great. If it didn't find anything it means that you've done a good job. Now run the installation for Nokia PC Suite and it should install just fine.
DEAR NOKIA!!
I've been googling for a solution like this for a week with no answers *anywhere*, including your message boards. Is it *this* hard to make the Cleaner *actually* delete all registry entries and files? Come on!