I have pci-e speed problems too in my Asus P7P55D Deluxe mobo, i7-860 prosessor and Radeon HD 4870 combination.

When I warm reboot pci-e speed is almost every time x8 mode and when stressed (ie. game stop respondin and I have to force reboot) it could be x4 or even once it was x1.
Drivers, bios and any other software not seem to have any impact in this issue of mine, IMHO it is somehow temperature related.
Every cold boot pci-e speed is ok. And comp.case open help too, even I got good ventilation in my case.

When I see my pci-e is ie. x8 I put PC to sleep for 10-20 sec, after that pci-e speed is correct x16.

@diogenesbr: Have you find out solution to your problem?