Had this same issue.

What caused it was that I set "Permission to Connect to database engine" to "Denied" in a different Active Directory group. This was in the Login Properties -> Status.

What I did not understand is even if a user is in a different Active Directory group that is Granted access, the Deny access in the other AD group takes precedence. Any user in the "Denied" AD group will never be able to login no matter what other AD groups are granted access.

The error messages are the same as above... wish Microsoft would put an error in saying "login denied access due to permissions" or something like that.

Good luck!