The types of registry problems can vary quite a bit. The most commonly reported are entries that are orphaned, meaning they reference something that doesn't exist on the computer (like remnants of a program that was uninstalled). It's not really a problem leaving them behind. Is it OK to remove them? Probably.
Where I think a lot of these cleaners go wrong is that they get too invasive. They look at entries that aren't referenced by anything and expect it is OK to remove them. However, I've been told by some techies that these cleaners will remove keys that were there by default from Microsoft. Usually removing them isn't a problem, as worthwhile programs will be intelligent enough to check for registry keys it relies upon, creating them if it doesn't find them. But less robust software will be tripped up and either fail or not work quite right, leaving the user quite frustrated.
