The answer depends on the situation. You can rename a domain only in a Windows Server 2003 mode forest, and although the actual rename of a domain is fully supported via the RENDOM tool ( http://www.microsoft.com/technet/downloads/winsrvr/domainrename.mspx ), other applications in the environment might not be so forgiving of a domain rename.
Tools are available to help resolve domain rename problems related to Microsoft Exchange Server (XDR-fixup.exe), Group Policy, and DFS, but other products aren't so supported. For example, neither Microsoft Systems Management Server (SMS) nor Microsoft SharePoint Portal Server support domain renames; you must reinstall them after a domain rename. However, if you migrate to a new domain you'd need to reinstall these products anyway. The bigger concerns are around other applications that interface via the NetBIOS or DNS names. A large part of the project for either a rename or a migration is discovery of the applications in use and how they interact with Active Directory (AD).
A domain rename usually takes a shorter time to actually implement because you don't move resources, but it poses more risk; if something doesn't work after the rename, there's no going back. A domain rename requires a huge amount of testing.
The ultimate decision must weigh tolerance to risk against time available. But with either method, you might need to reinstall some applications.