I'm having the same trouble with our new PE6600. This is ridiculous - even our RISC boxes don't take this long.
I note that there's an A16 BIOS available now - guess I'll try that and see if it helps.
One option to temporarily increase boot speed is to turn on the 'OS Install' option in the BIOS setup. This option limits the system memory to 256MB so it's not a permanent boot speed fix. Once the installation/diagnostic work is done on the machine, the option should be turned off.