Solution 1:

We have just upgraded three DL580 G7's that are model 584084-001 to Xeon E7-4870 processors. We found that what mattered in our environment was the revision of the main system board (not the CPU board/tray or SPI riser). After reading that last response, I checked iLO to verify all of our PAL versions. We do have one server that is running 4 E7-4870 processors with 1TB of memory on a CPU board with PAL version 0x10.

We found that as long as the system MainIO board (hp part 512843-001) is revision 0B or later, it works. Two of the three servers had revision 0A of the MainIO board and they would not post with the new processors. On those systems, all we replaced was the mainboard and the result was a working server.

Everything just worked on the server with the newer MainIO board revision, so we initially tried moving its CPU/Memory tray to the servers that were not working. When they still failed to work we decided that the issue lied outside of the CPU/Memory tray. The revision on the MainIO board was the only difference between the non-working servers and the working one.

We ordered the mainboards from our usual supplier, but had no way to specify revision. We just ordered and then verified the revision before installing.

EDIT: Adding the diagnostic info on our working CPLD / PAL versions:

Server 1:
 - CPLD PAL0:   ProLiant DL580 G7 SPI Board PAL version 0x0F
 - CPLD PAL1:   ProLiant DL580 G7 MainIO Board PAL version 0x0F
 - CPLD PAL2:  ProLiant DL580 G7 CPU Board PAL version 0x0E

Server 2:
 - CPLD PAL0:   ProLiant DL580 G7 SPI Board PAL version 0x0F
 - CPLD PAL1:   ProLiant DL580 G7 MainIO Board PAL version 0x0F
 - CPLD PAL2:   ProLiant DL580 G7 CPU Board PAL version 0x0F

Server 3:
 - CPLD PAL0:   ProLiant DL580 G7 SPI Board PAL version 0x10
 - CPLD PAL1:   ProLiant DL580 G7 MainIO Board PAL version 0x11 bootleg
   0x10
 - CPLD PAL2:   ProLiant DL580 G7 CPU Board PAL version 0x10

Solution 2:

This is a "call HP support" situation.

That is all.

Regardless of your warranty status, you're trying to make something work that requires specialized knowledge. I'll assume you've upgraded all of the firmware, but it also seems like you've recognized, but ignored a serious compatibility issue.