Samba – Configured Samba to join our domain, but logon fails from Windows machine

I've configured a Fedora 11 installation to join our domain. It seems to join successfully (though it reports a DNS update failure) but when I try to access \\fedoraserver.test.mycompany.com I'm prompted for a password. So I enter adminuser and the password and that fails, so I try test.mycompany.com\adminuser and that too fails. What am I missing?

EDIT (Update 9/1/09): I can now connect to the machine and see the shares on it (see my response to djhowell's answer) but when I try to connect, I get an error saying The network path was not found. I checked the log entry on the Fedora computer for the computer I'm connecting from (/var/log/samba/log.ComputerX) and it reads:

[2009/09/01 12:02:46,  1] libads/cldap.c:recv_cldap_netlogon(157)
    no reply received to cldap netlogon
[2009/09/01 12:02:46,  1] libads/ldap.c:ads_find_dc(417)
    ads_find_dc: failed to find a valid DC on our site (Default-First-Site-Name), trying to find another DC

Config files as of 9/1/09:

smb.conf:

[global]
Workgroup = TEST
realm = TEST.MYCOMPANY.COM
password server = DC.TEST.MYCOMPANY.COM
security = DOMAIN
server string = Test Samba Server
log file = /var/log/samba/log.%m
max log size = 50
idmap uid = 15000-20000
idmap gid = 15000-20000
windbind use default domain = yes
cups options = raw
client use spnego = no
server signing = auto
client signing = auto

[share]
comment = Test Share
path = /mnt/storage1
valid users = adminuser
admin users = adminuser
read list = adminuser
write list = adminuser
read only = No

I also set the krb5.conf file to look like this:

[logging]
default = FILE:/var/log/krb5libs.log
kdc = FILE:/var/log/krb5kdc.log
admin_server = FILE:/var/log/kadmind.log

[libdefaults]
default_realm = test.mycompany.com
dns_lookup_realm = false
dns_lookup_kdc = false
ticket_lifetime = 24h
forwardable = yes

[realms]
TEST.MYCOMPANY.COM = {
 kdc = dc.test.mycompany.com
 admin_server = dc.test.mycompany.com
 default_domain = test.mycompany.com
}

[domain_realm]
dc.test.mycompany.com = test.mycompany.com
.dc.test.mycompany.com = test.mycompany.com

[appdefaults]
pam = {
 debug = false
 ticket_lifetime = 36000
 renew_lifetime = 36000
 forwardable = true
 krb4_convert = false
}

I realize that there might be an issue with EXAMPLE.COM in there, however if I change it to TEST.MYCOMPANY.COM then it fails to join the domain with a preauthentication failure. As of 9/1/09, this is no longer the case.