If you ask me best thing to do is back up all your important files and do a complete reinstall of your OS. That'll get rid of it (100%) if you've exhausted all other options.
That's why I keep my OS and programs on my main HDD and my files (anime, school work, projects, driver setups, etc) on my slave. And my laptop's HDD is partitioned, so I'm able to do this on there too.
That's completely unnecessary! That's what my 85 year old grandfather does every time his computer doesn't work exactly the way he wants it. VERY RARELY is a reinstall of OS needed, and it certainly isn't worth it for a few random pop-ups. Reinstalling your OS is admitting defeat and letting the problem win. If it's not a really serious problem then it's better to struggle for months to fix it than it is to reinstall the OS. The reinstall CD should come with instructions "Bend over; Insert CD; take it like a (fill in the blank)".
CCleaner takes care of all the internet and registry problems. Cookies, cache, and temp files are the biggest reason for getting errors, stolen ID, pop-ups, and tracks. Occasionally your browser will require some registry cleanup as well (I had to modify IE8 registry file to stop my computer from trying to load an active desktop that I never set up).
Just grab some anti-spyware or pop-up blocker software and it will most likely fix it. Perhaps you already had a pop-up blocker that is no longer compatible with the new version of Firefox. So far the only things you say to have done is run CCleaner (probably on default settings so you really didn't clean anything more than what you could clear in Firefox browser by hitting 'clear history') and search for spyware. 9 times out of 10 it's the specific sites you are visiting that are auto opening a pop-up advertisement. A good ad blocker or pop-up stopper will end the problem.
More things to consider:
Have you tried running Firefox in safe mode for a while? Did it solve the issue? If so, it could be plugins, add-ons, or internet files causing it.
You SHOULD have at least one other internet browser, so have you browsed the internet with IE or whatever? Do you still get pop-ups? If not, then the problem is Firefox specific. If you do still get them then most likely it is something deeper in the computer like spyware, a virus, a process, or a program.
Are you going to a porn site habitually that would continually infect your browser with ads? (doesn't have to be porn I guess) If so, STOP GOING. find something safer or find a program to block what it's sending you.
If the problem is specific to Firefox, you could always try a reinstall of Firefox.
But for the love of God!!! DON'T let the problem rape you into reinstalling OS
