I know, what does the terminal server have to do with a GP password?
Well Dynamics GP uses the User ID and the server name in the ODBC connection as part of the hash when encrypting the user password for the first time. In our case, one of the terminal servers had the SQL Server as a fully qualified domain name and one just had the server name. So the weren't exactly the same and it broke the ability to decrypt the password.
This is also why user logins are case sensitive. The ASCII characters are different for upper and lower case letters so different information is passed when encrypting upper case vs. lower case passwords for the first time.
To solve our little problem we made both server names identical in the ODBC setup and then we reset the passwords of the affected users.
Huge thanks to Rob Mitchell of I.B.I.S. for the background behind this. He is the one who actually solved this issue.
*This post is locked for comments