The same MXD can be opened on machines that have Windows 10, but had ArcGIS Desktop 10.3.1 installed 'after' the upgrade.
Have you tried doing a repair on the install on the machines that are having issues? That is, start the install and select repair.
I know when I upgraded one of my machines from Win7 to 10, many of my files for various programs were put into a "temp" folder and I had to move them back into place, but doing a repair (or just an install) whould put the required files in the correct location...then look for any misplaced files you may have used to customize to see if they are still needed.