Tell us a bit about your network including whether it is all peer workgroups or domain and the operating systems involved.

Routers, switches, DNS servers etc.

Public or private address ranges?

Private address blocks being:
10.0.0.0 - 10.255.255.255
172.16.0.0 - 172.31.255.255
192.168.0.0 - 192.168.255.255
and also
169.254.0.0 -169.254.255.255 (which is generally reserved for automatic IP addressing - http://www.duxcw.com/faq/network/autoip.htm

Could be as simple as a router not being configured to assign more than a few addresses.