What problems are you having when trying to re-add the computers to the domain ?
I don’t think you need to create a new domain, but <b>I’m sure more useful responses will come if you tell us why you are unable to do this (what are you doing, and what error messages are you getting).</b>
First things to check:
– Computers can “see” the domain controller (ping it)
– DNS is properly configured
– You are using a valid domain account when trying to add the computers to the domain.