I could not for the life of me join a machine to the domain until I set the DC (SBS2k3 R2) as the local DNS (and DHCP) server, and disabled those services on my Smoothwall. Once I did that, everything JustWorked (TM).
Excuse my ignorance, but what do you mean by "Smoothwall"? Is that your router? I just checked mine and it has the DHCP server option enabled and I don't even remember if DHCP is enabled in the server as well. In this case looks like I might have a conflict. I'll check this when I get home and report it here. This is very interesting!