also bear in mind that if the number of PC's you have is very close to the macimum number of addresses your DHCP server provides.. it may be that the DHCP server still thinks some addresses are in use.. the lease may not have expired on the server.. and it will therefore not assign those addresses to any other computer
this is further backed up by the fact that you only seem to be able to get one IP address on a /renew..
you could always add another subnet to the DHCP server.. see if that makes a difference
