Outlook 2007 - cannot create profile after upgrading to 2008 R2 AD

Upgraded domain from 2003 to 2008 R2 native.
1 Exchange 2003 server

Outlook 2003 clients can create new profiles to exchange 2003 with no problems.

Outlook 2007 clients - existing profiles work fine - if try to create a new profile manually, get to check name stage, and it keeps prompting for password.  It will not accept the credentials, it just keeps prompting.  Tried on several client with several different mailboxes.

Discovered that if during profile creation I click on More Settings, Security tab, and set the authentication to NTLM, and set the option to prompt for username/password everytime - then it will prompt for credentials and accept them.  

Also interesting is the fact that once this new profile is created and opened one time, then I can go back to the security settings and set them back to negotiate authentication and uncheck prompt for password and it will work fine.  This explains why the existing profiles all work (because they all have default security configuration).

I am not 100% sure that this happened immediately after domain upgrade to 2008 R2, but I suspect that it did.  All I know is that it worked recently.  They have only been upgraded for 2 weeks now.

Also, our plan is to migrate them to Exchange 2010.  So I figured this may just be a problem with the Exchange 2003 server.  So I went ahead and installed the Exchange 2010 in coexistence.  I have the same problem with mailboxes on both exchange servers.  Exact same symptoms.  That is why I think it has something to do with AD.

Also, just found out that activesync has an issue now too.  There is one user that uses activesync on his iPhone.  Trying to get clarification of exactly when, but at some point recently it stopped sync'ing.  It keeps prompting him for his password, and tells him it is incorrect.

Sorry for the long description, but hoping someone can point me in the right diretion!

Thanks