Craig, are you sure it's actually trying to boot off the recovery disc? If it's a DVD burner, try changing to a different sata port.
I had a similar problem where the BIOS showed the desired boot order, but nothing I did could make it boot off the first drive... Turned out the CMOS battery was flaking out. I changed it, reset BIOS to default settings, set desired boot settings, saved and restart -- and it worked fine after that (The previous steps are worth trying also even if the CMOS battery is good. Restoring to default can 't hurt - and can sometimes fix a corrupted bios).
Another quick thing to try: Unplug the AC power, then hold in power button to drain any static electricity from the board.
Good luck!