That might be the case if you are using an illegal key.........
Is your Windows 8 install legitimate?
Volume licensed installations of Windows 8 are not eligible for the store upgrade. If your environment is licensed through a volume licensing agreement, you will need to access the Windows 8.1 media through the Volume Licensing Service Center.
Brandon
Windows Outreach Team- IT Pro
The Springboard Series on TechNet
A friend of mind brought his Windows 8 disc which he bought at Staples and installed on my computer.