Seriously, I go on holiday for a few days and the standards drop in this place ....
Mike-Bracknell's (or Saab's for that matter) very first question to you should have been ....
Have you tried to put a head on the headless machines ? What happened ? Do they have internet connectivity ?
Have they been powered-off/rebooted since the network reconfig ? If not, do it.
Can you also confirm the headless machines are wired and not wireless. If wireless, remove that aspect from the equation before proceeding further.
Can you also confirm you are only running one router or other DHCP server device on your network. If not, pick one and stick with it. Two DHCP servers on the same subnet is only for the gurus, and even then, its to be avoided where possible due to the sheer headaches it can cause if not properly configured.
Otherwise, Sir Mike is along the right lines ....
N.B. I'll give you the benefit of the doubt that the headless machines are actually turned on and physically connected ok !