I know this thread is a few years old but some enterprises are still using 10.1. I've just had the same issue as you guys, though whilst upgrading to 10.3.1 and was able to get past without uninstall/install.
Here's what I had:
2 x AGS in multi site configuration (10.1)
1 x network service account
1 x network share configuration store
Here's what I did:
I noticed that even during the upgrade to 10.3.1 it was using the correct AD service account and I had confirmed that my password for the service account was correct. I had noticed that it had originally been installed using the local arcgis account.
Firstly I tried setting the ArcGIS for Server service running as a local user, then resetting it in services to AD service account. Unfortunately this didn't work. In the local computer management on the first server I was upgrading I disabled the arcgis user. I then started running the post install and it allowed me to change the user, possibly because the the arcgis user was disabled. I didn't complete the post installation and instead tried going back into the installation, entered the appropriate network password for the AD service account, and it worked! No Invalid Password error.
The installation proceeded until it came to Starting ArcGIS Server service... and hung there for 10+ mins. I stopped the ArcGIS Server service in the windows services dialogue, and the installation was able to finish.
No issues with the password entry on the second server in the AGS site, but it did hang when trying to start the service again.
Hopefully this helps someone!
D
This 100% worked for me.