Up till recently, I have also used a PW with a '!' in it and it's been fine, even on sites after an upgrade to AT 4.0. However, I did a fresh Joomla 3.6 install this morning, and added AT 4.0. Added the Master PW as per usual, set all to YES and saved. After that I was completely locked out of doing anything in AT. The site operated fine, but I just could not set up AT. Deleted, reinstalled, same. Didn't try a double installation as was suggested.
So I deleted again, and installed an older version 3.xxx something, and it was fine. This time, when doing the Master PW, I made it without special characters. Then upgraded to 4.0 and everything is working fine. I've been noticing your warning about special characters during installs, Nicholas, but have continued, successfully, to use them. After all, we're taught to make PWs difficult.
Anyway, this isn't a support request, but some testing results for you. Seems that, maybe, special characters have caught up with us.