Your trust failed due to the combination of Windows 2008 R2 considering the WinNT security protocols insecure and the Forest Functional Level being anything higher than Server 2000 Compatible. Since this is a brand new 2008r2 domain, your functional levels are at Server 2008 R2. To the best of my knowledge, you can't downgrade those so your're stuck.
Samba can do this, but the answer isn't pretty, and it isn't secure. The trick is to let pam handle the Samba connections. The prime downside to this is that passwords are transmitted in the clear, which some Windows versions (anything newer than XP) won't allow without explicit configuration.
You'll have to configure winbind to talk to the NT domain, and then use LDAP to hunt the Active Directory domain. Then set both pam_winbind and pam_ldap to be sufficient for login. And finally configure Samba to use pam ('obey pam restrictions' directive). You'll also have to ensure that accounts in the NT domain are removed once they're migrated to the 2008r2 domain otherwise PAM may pick the wrong account to authenticate against. Once you're done, you can get Samba joined up properly to the 2008 domain, undo the pam directives, and passwords will be secure once more.
It's ugly, but it just might work.