Check power input to card, maybe a bad ground, if you have a second pic-e connector try it.
Also remove any other Pci-x devices if you have any until remedied.
You do have enough watts available on your power supply right?
Shouldn't be an issue but check bios to make sure Peg is selected for video and the IGP is disabled. It should disable automatically with the discrete card in but check.
I just upgraded my power supply thinking that it was the problem. Still 4x however, although last night I kept getting lock ups where the mouse cursor first appears with the new psu it worked first time. I will go into the bios and double check all of those things, I know I tried the peg setting.
I can find no logic in what's happening since you seem to have good power. There are enough pci-express lanes to run a single discrete card at by x16. Again nothing hooked to seconday ports usb or pci right. As the next thing I would pull the video card and examine the slot with a magnifier for any debree left from manufacturing. Also exam the contacts on card for anything similar. After reinstalling use optimal defaults in bios reboot and follow billbat's description. Doesn't seem reasonable to be a driver issue as the by x16 should work with default windows drivers or Catalyst when your measuring with GPU-Z. Actually out of curiosity try running CPU-z as that also displays the link width just to see if it agrees with sister program.
I swapped out the mobo and everything seems to be running nicely now.
A third (I have tried the 5850 a 4850 and a 4670) card in the gigabyte board says that it is running at 4x on the pci slot as well. I haven't heard from gigabyte as of yet. At least the 5850 is up and running well.