How to reinstall OS X when Recovery isn't working?
My recommendation would be to completely wipe the existing OS so that the OS X installer does not give you any errors about "upgrades".

As mentioned by Apple, I would boot the Mac while holding Command (⌘)-R. Once you are in OS X Utilities, select the Disk Utility option. In Disk Utility, select the drive containing the existing Macintosh HD partition, and then click the Erase button. Format the drive as OS X Extended (Journaled) with the GUID Partition Map. Once the drive has been erased and reformatted, exit Disk Utility.

Back in OS X Utilities, you should now be able to select Reinstall OS X which will guide you through reinstalling OS X Mountain Lion on the freshly reformatted disk without giving an error about any existing OS.