The problem was tracked down by Bob Arendt and Arjan's made a special P4P800 boot iso available which contains a workaround:
http://people.redhat.com/arjanv/asusp4p800-boot.iso
Gory details:
https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=121819
Cheers,