So, it seems to be a known issue – if you had Microsoft Office 2013 Preview, and uninstalled it, and installed Microsoft Office 2013 Professional Plus, and THEN tried to install Microsoft Visio 2013 or Microsoft Project 2013, you’ll get an error message that, literally, "you cannot install Microsoft Office Visio 2013 Professional Plus, since Microsoft Office 2013 Professional Plus" has NOT been uninstalled.
Now, that makes sense, doesn’t it?
I just lost 2 hours trying to solve the problem. I tried uninstalling Office 2013, and installing Visio 2013, and it worked, but it would not let me install the Office again, this time the error message was that "It cannot install Office 2013 as long as Visio 2013 is installed". That makes even more sense. It’s Visio, or rest of the Office then.
Luckily, I found a patch. With OFFICE 2013 Professional Plus INSTALLED (yes, it MUST be installed, otherwise tool complains that "there is no Office installed"), run this tool. The tool will then uninstall the office (I anyway did it like three times today), and all the Office 2013 Preview crap that remained on computer.
After that, you can install Microsoft Office 2013 Professional Plus AND Microsoft Visio 2013 Professional plus (On the same machine **woohoo**).
http://support.microsoft.com/kb/2739501/en-us
