The domain rename operation is supported within an Active Directory forest if, and only if, all domain controllers in the forest are running Windows Server 2003 Standard Edition, Windows Server 2003 Enterprise Edition, or Windows Server 2003 Datacenter Edition, and the forest functionality has been raised to Windows Server 2003 or higher. Therefore, before you can rename a domain in your Active Directory forest, you must ensure that the forest functionality has been raised to at least Windows Server 2003.
have you gone through step-bystep-guide to implmenting domain rename?
http://download.microsoft.com/download/c/f/c/cfcbff04-97ca-4fca-9e8c-3a9c90a2a2e2/Domain-Rename-Procedure.doc