Use that link if your mobo is DEFINITELY a p4c800 deluxe and not a p4c800 or p4c800-e deluxe.
Your new cpu was supported from bios level 1017, so put the old cpu in,switch your machine on, and note the BIOS level reported on the POST screen.
If the number is lower than 1017, you need to upgrade the BIOS.
Ok got it. I was able to do it and flash the bios (big pain in the ass) but since I was running SCSI's and other ad ons I had to take it in so that they could redo the bios settings. I wish they would tell you this stuff on the website. Oh well I got it, and it's faster now. Thanks for your help everyone.