Auch wenn ich die Ursache dieses Problems noch nicht klären konnte, will ich hier eine kurze Beschreibung geben und eine Lösungsmöglichkeit aufzeigen.
Vor einer Serverumstellung hatte ich schon mal auf dem neuen System einige Testdatenbanken restored und schon ein paar Logins angelegt. Diese Logins hatten die Datenbanken als Default-Datenbank. Während der Umstellung wurden die produktiven Datenbanken (Full + Differential) auf das neue System restored. Die vorher angelegten Logins blieben erhalten. Alle weiteren Logins wurden angelegt.
Nur bei den vorher angelegten Logins bekamen die Anwender Fehlermeldungen:

Error: 18456, Severity: 14, State: 11.
Login failed for user 'Domäne\Konto'. 
Reason: Token-based server access validation failed with an infrastructure error. 
Check for previous errors. 

Dieser Abschnitt ist leider nicht mehr mit gültigen Links versehen. Alternativ verwendet man (Stand 2021) am besten MSSQLSERVER_18456!
Bei der Suche nach der Ursache habe ich zuerst die Liste der Status-Codes gefunden, welche sich ohne den Support bearbeiten lassen.
Hier findet sich noch eine weitere Auflistung von Status-Codes und Hintergründe zu anderen Fehlerursachen
Status 11 sagt also "Valid login but server access failure". Bei der weiteren Suche bin ich dann auf ein SQL gestossen, was mir die Berechtigungen der Logins anzeigt

SELECT t2.name,t1.*
FROM  sys.server_permissions t1 , sys.server_principals t2
WHERE t1.grantee_principal_id = t2.principal_id
AND t1.TYPE<>'R'
ORDER BY name;

Bei der Liste fiel auf, dass für die problembehafteten Logins kein Eintrag vorhanden war. Nun galt es nur noch die fehlende Berechtigung zu setzen:

USE MASTER
GO
GRANT connect sql TO [Domäne\Konto];

und schon konnten die User sich anmelden.