It sounds like you are trying to install an upgrade version on a clean disk/i.e. without a prior version of Windows installed. Unlike XP, which simply asked to scan a previous windows disk to verify eligibility for the upgrade, it appears Windows 7 actually insists on being installed on a disk with a prior version already installed.
I had the same problem last night. I got a terabyte hard drive since I had to do a new install. Initially I installed my upgrade Home Premium 64bit OS on the clean disk, only to be told that my key was invalid. I checked and re-checked the key. Even though each time it appeared to be correct, I re-entered it like 5 times with no success. This surprised me greatly, because I have the family pack, and had already installed it on my first machine with the same key with no problem. Customer service was closed, so I took a gamble, reinstalled XP after a clean format, then installed Windows 7 and validated with the same key with no problem.
I was severely (are you listening Microsoft) angry at my waste of time since it worked with XP. It seemed like a technological step back, and a much more complicated way of completing the task than Windows XP. I suppose they are doing it for Security purposes since it so easy to burn a great bootleg, and I know they didn't want to come out and say "hey, despite our roll out hoopla, hey "I'm a PC", Win7 is actually less flexible than XP when installing an upgrade version, but they should find a way to make this apparent to people before they wast their time. Maybe a stuffer in the OS box?????
Sorry about the rant at the end of my answer but GRRRR!
Hope this helped.