I received the above message while attempting to remove Active Directory from the last DC in a test forest child domain, even though the second-to-last DC demotion didn't produce errors.  The following article describes the procedure necessary to cleanup orphaned DC metadata from the domain: http://support.microsoft.com/default.aspx?scid=kb;en-us;216498

Completing steps 1 through 16 solved the problem - say goodbye, child domain...