Can Linux machines joined to active directory update its DNS records

The error 81 means server unreachable. Use err.exe from download.microsoft.com to lookup the error and you will see the following.

LDAP_SERVER_DOWN winldap.h

DNS is unable to create built in partitions means it was trying to create the DC=DomainDNSZones,DC=Domain,DC=Local and DC=ForestDNSZones,DC=Domain,DC=Local application partitions. To do that it would have to contact the domain naming master FSMO role holder (which is your only DC that you have). I wouldn't worry about this just yet as the zones (_msdcs.domain.local and domain.local) are likely stored in the domain partition at the moment beneath CN=microsoftDNS,CN=System,DC=Domain,DC=Local.

I would make sure you dont have any firewall software other than the inbuilt one. Have you got some 3rd party AV which bundles a firewall with it installed? You might want to turn all 3rd party firewalls off and then the Windows Firewall too (while you troubleshoot) as I dont know what firewall profile is currently active and what rules/traffic is allowed. Do you have more than one network interface on this machine?

open the wf.msc and on the left pane click the top most element and view its properties. Go through each tab for domain, public and private and turn them all off. DONT stop any Windows Firewall related services using services.msc.

Doing a "netstat -ano" will show what ports the server is listening on which should have entries indicating listening on TCP/UDP ports such as 389, 88, 135, 445 and so on. You need to see if you can connect to those ports from the relevant apps or some port scan utility such as portqry.exe from the Windows 2003 support tools or resource kit. Unfortunately its not bundled with the OS anymore but should work if you extract from the relevant download packages from download.microsoft.com.

The problem you're going to run into is that Active Directory uses DNS to tell client machines where to find various resources, so turning off DNS on the Windows server will eventually stop things that require Active Directory from working. It sounds like it worked for a number of hours because clients had it cached, but then the cache expired.

My suggestion would be to run bind on your Linux server, and make it act as a secondary to your Windows server, and then configure your DHCP server to give out the Linux server as the DNS server clients should be using. That way, your DNS queries are offloaded onto the Linux server whilst retaining the ability to use Active Directory.

You'll need a line in your named.conf (or such) a bit like this:-

zone "ad.internal.company.com"
{
  type slave;
  file "/etc/bind/db.ad.internal.company.com";
  masters { aaa.bbb.ccc.ddd; };
};

Not sure which version of SBS you're on, but for 2003, open up the dnsmgmt console, go to the properties for your active directory domain, and add your Linux server as a nameserver on the Name Servers tab. You'll also want to make sure Allow zone transfers is ticked on the Zone Transfers tab, along with Only to servers listed on the Name Servers tab. Additionally, you'll want to make sure that when you click Notify... (also on the Zone Transfers tab), that Automatically notify and Servers listed on the Name Servers tab are selected.

Reload (or restart) bind on your Linux server, and keep an eye on the logs, and you should see bind requesting a copy of the zonefile from the Windows server. To make sure everything's working, try making an addition to the zonefile on the Windows server and make it's propagated to bind on the Linux server.

Hope that helps!