I am having the exact same problem.
I have checked the logs on the DC and the XenApp server, and it looks like the gateway is not passing on the authentication through. I did another test: created a new user, and added it to the Citrix group used in Radius, and I was able to logon almost instantly!
Also, logging on to the Web Interface directly works fine for the users who can't authenticate through the CAG. Hopefully someone else's seen this issue and can give some suggestions.
George