This is still broken as of Wheezy 7.0.0. Just wasted quite a few hours suspecting it was a BIOS bug, then found this, which appears to exhibit exactly the same "works when there's a CD present" behaviour.