Okay, changed the pram battery ($20.63 boy do I love Lake Placid's Radio Shack), reset the pmu, pushed the power button and up she booted on the first try.
I tried doing a restart and the problem is still there,. It took about ten tries to get it to startup.
That's no good... try zapping the pram now. Wow, that battery price is pretty steep... I know the pram should have reset when you changed the battery, but in this situation zapping it again might not hurt. Can you do a safe boot?