Please invoke this on one of the problematic client hosts:
dig in a debian.org +trace +recurse
dig in a google.com +trace +recurse
What is the output of 'ip addr ls' and 'ip route ls' on one of the Linux
clients? What are the contents of /etc/resolv.conf and /etc/hosts on one
of the Linux clients? What are the contents of /etc/bind/named.conf*
(that is, all the configuration files with names starting with
/etc/bind/named.conf)? What is the actual output where you see errors?
For example, if nslookup fails, please provide the complete command-line
and the complete error output. Same for apt-get or any other thing that
is failing.
What domain name did you choose for your local area network?
What software are you using on the DNS server? How is it configured?
Did you use a combined nameserver + recursive resolver on a single
host, or did you separate the functionality?
Plus, all the other excellent questions others have already given.
In short, you must give details. All of the details.