I have downloaded a trial version of TuneUp Utilities 2007, and was working fine after i completed the registration process. Next day, while using it, it dislpayed a pop up message:

Everytime i enter it, it says that this was correct, and it requires rebooting. But again, it displayes the "Not genuine" message. What can i do to fix this problem?

I think its an error in the codes supplied on the page, I guess the only thing you could do is contact the support on the site in question and ask them whats going on.

If you're using a pirated serial, then most likely between when you installed it and now, it downloaded an update which nullified the blacklisted serial. If, on the other hand, you actually bought an original copy, then your first recourse should be to call the company and have them solve your problem.

You could also try uninstalling, and reinstalling the program. It can help, if you do it make sure you remove registry traces and files.
Just remeber your registration key, if it IS a geniuine key and it isn't working after a reinstall then you will probably have to contact support and sort it out with them. If it ISN'T a geniune key then you need to buy the software if you want to use it.

I've heard of sometimes when you install a demo version of a program then register it, the way it handles the registration can cause conflicts with the demo version and produce an error.

Anyways hope it helps
-HellFire