So I'm guessing you've searched all the posts on UAM in this forum - if not, then a good place to check.
Based on what you've said, I think problem is imc. How are your user credentials coming over? via LDAP from AD?
Are you using the synchronize users as needed switch? If so try turning that off. I've had some odd things happen creating users on the fly. Instead, set up the periodic sync, and run manually as needed.
Another thing to check is the user stack, authentication settings. Are these only windows btw? Check and make sure if the validate certificate setting is checked, then a matching trust cert for you domain is in the list. It should work unchecked - just be consistent. Also maybe try a mac or linux client if you can.
If you are using any of the modifiers, or other features related to time of day, location etc., in your policies - simplify as much as possible. Get the basic working if you aren't there already.
Its been a while since I got this all working so I don't recall all the problems I had along the way. I've posted configuration info for what worked for me in earlier posts.