Role synchronization is the major culprit and the reason why Tam only did it on the first time a user visited the site but the majority of users wanted it to happen everytime a user visited the site. Adding nested group searching slowed it down even more. The more DNN roles/larger the AD is the longer it's going to take to go through the synchronization process. It's a trade off at this point.

I do have some ideas on how to speed it up but it's going to take a rewrite of a large amount of the code (something I'm wanting to do anyway).

Yes it will.

The number of users isn't the problem but it's the number of groups in the AD.

When you did the settings did it see the sub-domain? In theory it should work but I don't have a sub-domain to test with so I've never been able to verify/code for it.