Microsoft Office 2007 Enterprise Installation Issue

I just got Microsoft Office 2007 Enterprise. Unfortunately, whenever I try to install it with my product key on my computer, it gives me an invalid key message. I tried it also with my brother's newly purchased which has no Microsoft Office software. I continue to get the same message with his product key as well. I read somewhere on Microsoft Support that if an older Office program is installed this might be the issue, but I reformated last month and there are no traces of Office 2003 left (In registry, etc. from what I see). I've taken all the steps so far such as even looking in Add or Remove Software and yet nothing. I've had a few good friends look at it too who are the equalvialent of IT educated and they can't figure it out either so far. I've considered contacting Microsoft support and it would cost $99 USD or something like that and it's redicilous. Any help PLEASE?  

-----------------------------
*My PC meets all requirements to run Microsoft Office