******Begin User Part 1******
...[Server is] a Dell PowerEdge 600sc server with RAID 1. There is 1
NIC. SBS 2003 Standard came pre-installed by Dell. I plugged the server
onto a network that is sharing a public IP in a NAT configuration on a
Sonicwall Firewall, which is also the DHCP server for all PCs on the
network. I configured the NIC on the SBS server with a static IP
address. I configured the DNS server with forwarders to the public IP
addresses of the DNS servers of the Internet provider. And I made the IP
address of the new SBS server the primary DNS server assigned by the
DHCP server. PCs on the LAN, using the IP address of the SBS server as
their primary DNS server, were not able to get DNS resolution. But the
server was for itself.

Here is the response I received from Microsoft:
******End User Part 1******

******Begin Microsoft******
The configurations in SBS 2003 is simialar to configurations in SBS
2000.
There is no need for you to run ICW.exe on the computers.

This issue can occur because Extension Mechanisms for DNS is enabled on
Windows 2003 by default (it is disbled in the Windows/SBS 2000). (The
SBS 2003 is based on the Windows 2003)

828731 - An External DNS Query May Cause an Error Message in Windows Server 2003:
http://support.microsoft.com/default.aspx?scid=kb;en-us;828731&Product=w

Please try the following command to turn off EDNS0 support 1. Start a
command prompt.
2. Type "dnscmd /Config /EnableEDnsProbes 0" (without the quotation
marks), and then press ENTER.

Then please check the issue again. You can take a look at the following
URL for more information: 828263 DNS query responses do not travel
through a firewall in Windows Server
http://support.microsoft.com/?id=828263
******End Microsoft******

******Begin User Part 2******
The settings changed that is recommended by Microsoft disables Extension
Mechanisms for DNS that is supposedly blocking the computers using this
DNS server to get their name resolution. So disabling this thing then
allows proper resolution.

Apparently, Extension Mechanisms for DNS was disabled by default in SBS
2000, but Microsoft changed that in 2003 to make it more secure.
******End User Part 2******