<soapbox>
Testing must be an integral part of every upgrade effort.  And, given the size of the project at hand, reliable test automation is a requirement.   Even with automation, the testing processes require a lot of highly skilled work to define, setup and use effectively and reliably.  A strong QA manager and experienced team will be absolutely critical to this effort. 
</soapbox>

Here are some of the things GM offers to facilitate testing:
And there are still four huge gaps that must be closed:
 
1) strong QA/User support for creating detailed test scripts -- this takes a deep understanding of the data, dynamics, and use of the system.
2) strong DBA support including automated test data management -- making sure the data in side-by-side environments is ready and valid for the expectations of the test scripts
3) strong SCM and deployment and environment support -- ideally continuous integration
4) If we are expected to ensure functionally correct code, we will need a development testing area -- an environment to get up close and personal with the old and new code (i.e. in a debugger and valid test data)

<soapbox>
The Users, the QA team, and the support teams should be able to routinely complete a fully documented, successful, automated regression test of the legacy app before they try testing the new app.  That will keep them gainfully busy for quite a while, so we can focus on getting them a solid runnable, testable new app for testing.  And it will help us maintain momentum once testing starts.  Beware: The customer might decide to cancel the project before it starts if they realize they cannot rigorously test what they already have.
</soapbox>

One more comment: one way to mitigate testing pressure is to break the codebase into smaller parts that can be upgraded, tested, and deployed independently. Some codebases allow for this and some don't.  This approach makes for a longer, more complex transition where the customer exists in a hybrid state using and maintaining a mix of old and new until the last component is upgraded.  Some customers are already in this state; so, they may be more accepting of it.  The gradual transition approach can make re-engineering more complex because the new codes might have to integrate with old components in production.