It's hard to say without knowing more details. When you do a "service named restart" do you see any errors at the end of your /var/log/messages file indicating a problem? Do you have an up to date root cache file? Is your /etc/resolv.conf file right? I wrote a tip on setting up DHCP and Dynamic DNS on Red Hat 8.0, don't know if it will help. You'll find it on my web site (Void's BS, like at bottom of message).
[edit]
Ooops, I thought I read you were running a DNS server and it wasn't working. Now I see it looks like you are only running a client. Sorry about that... Check your /etc/resolv.conf file and make sure it's properly configured.
[/edit]
[ January 17, 2003: Message edited by: void main ]