Could not open Visual Studio 2013 for project C:/UnrealEngine4_Full/UE4.sln

I had the same issue. Your ENV variables are still pointing to the wrong folder.

For example, my non working variables were:

VCINSTALLDIR = C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\
VSINSTALLDIR = C:\Program Files (x86)\Microsoft Visual Studio 10.0\

Which needs to be

VCINSTALLDIR = C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\
VSINSTALLDIR = C:\Program Files (x86)\Microsoft Visual Studio 12.0\
VS120COMNTOOLS = C:\Program Files (x86)\Microsoft Visual Studio 12.0\Common7\Tools\

are you 100% sure uninstalling removed these folders?
Anwyays, hopefully that fixes you!