Hi Jesse,
The serial on the Maxbotics isn't really logic level serial. True, it does use logic levels, but it uses them in a way that allows a PC to be plugged in directlly. You have a couple of options to connect it to your AVR.
1 - Invert the Tx and Rx lines (using a hardware inverter).
2 - Stick a Max232 or similar between the maxbotix sensor and the AVR (treating the maxbotix sonar like an RS-232 level device).
I wrote up a page over here:
http://docswiki.gumstix.org/Serial_voltageswhich explains the differences between the various voltages. The maxbtox sensor is behaving like a device which uses "logic level RS-232".