I had this problem as well. I had Office 2013 32 bit via 365 Small Business Installed on Windows 8.1. Tried to uninstall from Control Panel, then install 64 bit version of Office 2013 Professional Plus. Got the message: Error 25004. The product key you
entered cannot be used on this machine. This is most likely due to the previous Office 2013 trials being installed. (System error: -214217387) Setup failed. Rolling back changes...
After many failed attempts following the suggestions in this thread, I stumbled across another MSFT KB that solved my problem: http://support.microsoft.com/kb/2739501. I reinstalled Office 365, then
ran the O15CTRRemove.diagcab program suggested in the KB. After I ran this, I rebooted, then I was able to reinstall my new copy of 64 bit Office 2013 Professional Plus with no error.
Hopefully, this helps someone else resolve this frustrating roadblock.