I ended up calling Microsoft support, and we spent about 45 minutes searching the registry for the particular version of NuGet (there was an old version installed that was not properly removed, keeping the new one from being installed).
We had to search by version id.
VS2013 does not only put things in:
C:\Program Files (x86)\Microsoft Visual Studio 12.0\Common7\IDE\Extensions
(with a random character folder name)
But also in %appdata%\Microsoft Visual Studio 12.0\Common7\IDE\Extensions
as well as other places. So we had a lot of searching to do, but once we found it and removed the folder and all the old Nuget references from the registry, it was possible to continue and install the new NUGET Package Manager.
Today I found things were corrupt, (probably registry) but a REPAIR (From the install) was able to fix the problems