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."