I was sure I never attempted to rename the original domain... Assuming a domain rename operation was in progress (why?!), I ended that operation with rendom:
C:\>rendom /end
The operation completed successfully.
After this operation, I could add my new slave domain controller. Jeej!