It definitely sounds like a issue with Group Policy Objects - also it's worth looking at any logon scripts, I have had similar issues for example when you have logon scripts set to run async, it will hang until the logon scripts have completely run. As mentioned enable verbose output on the messages.