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.

vsixinstaller.exe /uninstall:NuPackToolsVsix.Microsoft.67e54e40-0ae3-42c5-a949-fddf5739e7a5

This worked even though the phone version had reported as being installed successfully, and the Visual Studio had been the one with the error.