What motherboard do you have? Some combinations of motherboards and video cards simply will not work at AGP 4X. You have to drop down to 2X in your system's BIOS.

Have you updated your BIOS on the motherboard and video card?