Hi,
Do you mind telling us the error message when you re-installed? As far as I know, we can re-install the Office on the same computer without any issues. We can read this blog about the new Office 2013 licensing terms
https://blogs.office.com/2013/03/06/office-2013-now-transferable/
Then, if we have the installation copy, please try to install Project 2013 first and skip the activation during process. After installation is complete, we can use your key to activate by phone.
http://support.microsoft.com/gp/customer-service-phone-numbers/en-us
Regards,
George Zhao
TechNet Community Support