Thanks for the responses. I want to share my story, maybe somebody can learn from it:
In the end, I created a PTC ticket (system down, maximum impact, very short description) and they contacted me after an hour. (E-Mail said max.2 hours,)
They provided me with two links. The first one was to find the real reason and to confirm the LDAP error code 49 :
https://www.ptc.com/en/support/article/CS350915 Usage of BT LDAP Browser Client in Windchill PDMLink
There, you got to the folder: D:\ptc\Windchill_12.0\HTTPServer\conf
In the file app-Windchill-AuthProvider.xml you find the ncessary info to get that running.
After trying to connect, we got the same error (49) and therefore, PTC said, the password of that account in that xml-file was maybe changed.
If that would have happened, you need to follow the procedure in the following case to make it work again:
https://www.ptc.com/en/support/article/CS334240
Luckily, it was just some admin that moved the account of the xml-file into some other folder. This then made it impossible for Windchill to get the login info, which resulted in this error.
After moving it back to the folder (see the xml-file) where it was, everything was working instantly, users could log in again. No restart of anything necessary.