I had a deeper look into my above described issue.
It is KB3002657 that stops UltraVNC from being able to use domain authentication.
The only solution is:
1. Uninstall KB3000988 and KB3035132 from your Domain Controller (these updates are dependencies for the buggy KB3002657)
2. Uninstall KB3002657 from your Domain Controller
3. Restart your Domain Controller
4. Reinstall the two updates from 1. and restart your Domain Controller
After this you will be able to use "New MS Logon" again.
This is not the only issue that arises after installing KB3002657.
I also found out that Windows authentication for connecting to an SQL Server using ODBC will also fail (http://tinyurl.com/m89abus