Set Samba's preferred AD server at the PDC emulator for the domain.
You can change this after joining the domain, but it seems to work
best when you point at the PDC emulator when joining. I'd also
recommend creating the computer object in AD using AD Users and
Computers before trying to join the Samba server to the domain. If
you're running a 2008 domain I think there is a setting that needs to
be changed on the AD side to allow Linux (and other Samba servers such
as Mac OSX) to join the domain, but I don't recall what that setting
is.

Double check your kerberos realm. Kerberos realm is everything
following the @ sign if you look at the User logon name field in AD
Users and Computers. You may want to try using an account other than
the default Administrator account.


-- 
Andrew S. Zbikowski | http://andy.zibnet.us
IT Outhouse Blog Thing | http://www.itouthouse.com