You're not going to believe this, but I think I stumbled across a fix for this!
The problem appears to be in the user account information, which is why some people were working and some weren't. To put it simply, if you delete the account from DNN, and then log into DNN again it will create a new account and everything is neato-cool-and-groovy, everything works just like it is supposed to! (well, logging in does... I'll have to do more trouble-shooting on the other issues.
Anyways, tomorrow I'm going to figure out the table structures and then run SQL queries to "unathorize" all the domain users so I can then delete all unathorized accounts. Then I'll be able to let the accounts re-create themselves. Of course, that means I'll also have to spend time making duplicate AD groups to match the DNN security roles so everyone gets into the proper places in DNN....
Come to think of it, that sounds like a lot of work... But, if it gets everything working again, it will be worth it!