Give it a little time as possibly the change has not replicated to the other domain
controllers or try creating it on the same domain controller that you deleted it on.
If that does not work check the Event Viewer for any errors and run dcdiag on the
domain controllers looking for failed tests and other warnings as you may have a
replication/configuration problem. --- Steve