Are you running Premiere Elements 8 as the 8.0.1 Update?
Are the automatic Background Rendering and AutoAnalyzer shut OFF?
For Background Rendering option, please see Edit Menu/Preferences/General/ and "Enable Background Rendering" to make sure that it is OFF.
For AutoAnalayzer please click on Organzier tab in the row below the selected Organize header to open the Elements Organizer. In the Elements Organizer workspace, go to Edit Menu/Preferences/AutoAnalyzer options and shut OFF all the options there. To get back to the Premiere Elements workspace from the Elements Organizer workspace, go to File Menu/Exit.
Next, is your external hard drive "drive letter" changing on its own between projects?
Regarding the files that went into the project as source media...have they been moved from their hard drive save location or other altered after you saved/closed your project?
Also, are photos included in this project? If so, what are their pixel dimensions and how many of them are there?
We will be watching for your follow up and then decide what next if necessary.
Working with external HDD's can pose a few potential problems. The main one is the drive letter assigned to the external HDD. Depending on what else might be plugged in, and the order that the devices are turned on, can affect the assignment of that drive letter. The "trick" is to go into the OS and manually assign the drive letter. This process will differ slightly, Windows version to Windows version. I recommend going into Windows Help, and just searching for "drive letter," without the " marks. Follow the instructions there. Then, regardless of the order, or whatever else might be plugged in, Windows will always hold that drive letter for that external HDD, and it will always be the same, unique drive letter, so the absolute Path of your linked media files will not change.
This article goes into more detail: http://forums.adobe.com/message/4542396#4542396
This article might be useful for the "Where is file ____ ?" message: http://forums.adobe.com/message/4598705#4598705
Good luck, and hope that helps,