Ok guys, I finally got everything working (including the hard drive swap). Here's my story.
My xbox dvd drive was NOT able to read any of the CD-RW I put in. The brands I tried including Sony, Verbatim, Kodak. None of them works. So instead, I got a Y power cable and hook up a regular PC DVD rom to the XBox. I then put in a CD-RW from before, and the Xbox finally booted up!
So onto the hard drive swapping. I ran into the Error code 16 as well, just like zanderch. What happened was I swapped in the new hard drive during the evening, and I left the xbox powered off and unplug until the next morning before working on it.
After some googling, I found something about Xbox not able to find the time setting since the old hard drive is no longer there. So I put the old hard drive back in, and tried booting up with the same EvoX boot disk, and it booted up fine this time.
I then quickly unplugged everything and swapped the new drive back in, booted up using that EvoX boot disk, and I was still able to boot (without the error code 16). I then proceeded to using raw ftp commands to format my new hard drive (you can find the tutorial on xbox-scene).