I had the same issue with both Token-based and Login-based authentication.

Ive blogged my solution here:

http://dbamohsin.wordpress.com/2011/09/06/token-based-server-access-validation-failed-with-an-infrastructure-error/[/url]

if you dont want to read that then run this code for the user experiencing issues...

GRANT CONNECT SQL TO [DOMAIN\firstname.lastname]

GRANT CONNECT ON ENDPOINT::"TSQL Default TCP" TO [DOMAIN\firstname.lastname]