Opening the earler versions of peoject in the latest versions should not be a problem.
There are many links on this forums that also say the same. But still there are some limitations or guesses around this.
I would advise you not to uninstall Encore CS4. Both CS4 and CS5 can co-exist on the same system. This is because there might be some plug-ins that CS4 might be using and not CS5 which may cause some problem.
Other option could be to open your project and delete the menus in the project and re-import them again. But this is just a guess because most of the time I have seen menus causing problems from one version to other.
>project resides on an external hard drive.
Is the drive letter the same between old and new computers?
And, some general reading...
As well as the below, right click the Encore icon and select Run as Administrator, which is NOT the same thing as running the computer with the Administrator account, and which fixes several "odd" problems... To create a dual layer DVD (or a BluRay?), you MUST have Encore set to use the Run as Administrator option
Run as Administrator http://forums.adobe.com/thread/771202?tstart=0
Long File Names or odd characters cause problems
And This Message Thread http://forums.adobe.com/thread/665641?tstart=0