Chris,
I've just had the exact same problem and even a service request didn't solve my problem.
However, I figured it out... also on the DSP56858.
I created a new project using the example stationary for an internal bootloader and built it for the correct processor. You then have to pass this output file through Freescale's "srec_to_boot_format.exe" file in your C:\Program Files.... folder. This must be a binary file though. I've attached my subsequent binary file if it helps.
The micro then needs powering up and the file sending through hyperterminal (within 3 sec in my case) at 38400,8,N,1 (no flow control) by using Send text file, not send file. If you're using teraterm then make sure you tick the "binary" check box.
When this is sent you will receive "OK" in return, don't power down as it is now in bootmode and then send your output file for your actual project. If you don't get "OK" then no point continuing...
One final thing is MODA should be tied low, MODB and MODC to Vdd.
Hope this helps...
