Installing Project Server 2013 – Previous version of product exists

This error is not very specific.  It could mean project server 2010 or sharepoint 2010 exists.  If your uninstall doens't complete successfully (or it does but you don't realize it left some residual), then you may run into this problem.  The key to figuring this out is to run ProcMon.exe on the server when you attempt to do the install, then work backwards on all the registry keys that it tries to access.

In my case, because the HKLMSoftwareMicrosoftShared ToolsWeb Server Extensions14.0 registry key still existed, it thought that SharePoint 2010 was installed.  However, I had removed it.  Yes this residual registry key was preventing the install from proceeding.  Simply delete this registry key and your install will continue as desired!

Enjoy!
Chris