Server 2008 DHCP some clients not getting IP

Given the output that you are given here it appears that the Linksys router is handing all DNS requests up to the ISP's DNS server. Linksys routers do not have DNS themselves and don't 'hold' the names of the connected machines locally. Most likely your computers are using NetBIOS broadcasts to identify each other within the network, but there is no 'formal' name-to-IP mapping going on.

If you have the spare box, or an underutilized server one option could be to set up one box as a DNS server, have all your workstations point and register to that server, then have that server redirect to the ISP's DNS. If you cannot get the workstations to work by pointing their DNS requests to the router itself.

Is your Linux DHCP client asking for dynamic DNS update? I can't see any information in your question about that, and without it your Linux DHCP requests won't get DDNS registration on the server side. Look at the "DYNAMIC DNS" section in dhclient.conf(5) for details of the settings required.