FPGA configuration encountered errors. Program FPGA failed

In this case the solution was actually simple. The console window was actually displaying something like this:

The following sections did not fit into Processor BRAM memory:
Section .jcr (0x88000944 - 0x88000947)
Section .eh_frame (0x88000940 - 0x88000943)
Section .data (0x88000830 - 0x8800093F)
Section .rodata (0x88000814 - 0x88000829)
Section .dtors (0x8800080C - 0x88000813)
Section .ctors (0x88000804 - 0x8800080B)
Section .fini (0x880007E8 - 0x88000803)
Section .init (0x880007B4 - 0x880007E7)
Section .text (0x88000000 - 0x880007B3)

Try using the linker script generation tools to generate an ELF that maps
correctly to your hardware design.

Which is a common error. Normally you can just make the BRAM larger in the EDK and regenerate. If it is still not working other things to try:

Booting from somewhere else:
 http://www.xilinx.com/support/answers/43414.htm
Turning off ELF check if the ELF is too large:
http://www.xilinx.com/support/answers/38178.html
Completely deleting Linker Script and regenerating:
http://forums.xilinx.com/t5/Embedded-Development-Tools/elfcheck-failed/td-p/307699
"It looks like it's still trying to place the data and code into your BRAM.  Double check your linker script generation and manually delete the .ld file before rebuilding the workspace."