What BIOS do you have at the moment?
(if using EvolutionX as a dash, go to Settings menu to find out the BIOS)
My first thought when reading your post was a "cable select jumper" issue, but this would also stop you installing the software in the first place!
Here's what I do:-
Boot Xbox
Run "Backup" command from EvolutionX's System Utils menu
FTP to Xbox
Transfer everything from Xbox's C and E drives to a pair of folders on my laptop
Burn the backup folder together with a cut-down EvolutionX (lets you format the drive, run ConfigMagic, that's about it) to a CDRW
Shut down the Xbox
Swap the Xbox hard drive
Boot the Xbox with the CDRW in the drive
Format the drive
Lock the drive using ConfigMagic
Reboot (CDRW still in drive)
FTP everything back again, at this point the machine should be exactly the same as before, except with a bigger drive
Reboot the box with my EvolutionX Install CD in the drive
Install EvolutionX
There may be easier ways to do it (do I still need to re-burn the CDRW for each machine I do, or is this method obsolete?) but it works every time.