How to clean boot menu and check/clean mbr
Credit goes to @bmike for answering this one, but I wanted to answer it here so the question is closed. Marking as community wiki so that I'm not taking credit.

In this situation you will want to use the recovery tool built into the system's firmware, called "OS X Recovery". You can read Apple's documentation here. To start OS X Recovery, hold Cmd+R while you press the power button to turn on your computer.

This will download a full copy of OS X to install, so you'll probably want to hook your computer up to ethernet if it's at all available.