Simply uninstalling with "Add Remove Programs" may not clear the problem up - it didn't for me. Try the advice for "Cannot uninstall NuGet for Windows Phone Tools" in the known issues document, which basically says:
Windows Phone Tools does not have support for the Visual Studio Extension Manager. In order to uninstall NuGet, run the following command.
This worked even though the phone version had reported as being installed successfully, and the Visual Studio had been the one with the error.