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.