OK so same here went from v10.3.1 to 10.5.1 and did the install over the top of the v10.3.1.
What worked for us was to uninstall everything desktop related via the add remove programs.
Next did a search and destroy on any and all folders that referenced ESRI on the local machine to include each and every profile.
Also unloaded any other ESRI software such as Explorer / Arc Earth
Then we ran a registry cleaner to clear any and all references to pointers in the registry.
Still had issues - ripped out the SQL client driver and installed the ODBC driver that suits your version of OS 64 / 32 bit and database engine.
That has seemed to fix the problems for us - most notable was the "clean" install.
Here is where I removed ESRI / ArcGIS references:
C:\Program Files\Common Files\ArcGIS
C:\ Program Files(x86)\ArcGIS
C:\Program Files\Common Files(x86)\ArcGIS
C:\Python27
C:\Users\
I did find a few directories with just the name ESRI - killed those also
Oh if you see anything in the FlexNet directories leave that alone !!
Hope this helps someone