Is it really necessary to convert in both directions? It looks like to me that the arduino xbee shield does no conversion on the (arduino) receive end and only uses some resistors on the transmit side.
The MAX3221 looks like an rs232 transceiver. It goes in both directions, but not the levels the Arduino would need.
The easiest solution is to use a 3.3V part that says "5V tolerant inputs" in the datasheet. (: A few operate this way (e.g. the Vinculum VNC1L does, IIRC).
A solution I have in mind to try is to replace the 16MHz ATmega168 with a 10MHz low voltage version, and run the whole system at 3.3V.
On the receive side of the 3.3V device: One solution is to use a voltage dividing resistor network. Diodes can be used to clamp the voltage to acceptable levels.
On the transmit side of the 3.3V device: 3.3V is usually above the "on" level for a 5V input, so you can frequently get away with doing nothing. Use a transistor to switch a 5V load (much the same way you use a transistor to switch a 12V motor or relay coil).
For an integrated solution, there are dedicated devices; e.g. search Maxim for level translators.
XBee is not 5V tolerant (some users tried it and it works, but was never confirmed by Digi to be 5V tolerant). You only need to convert the 5V from Arduino signals to 3.3V, using a voltage divider using 10K and 15K resistors. You can connect the signals from Xbee to the Arduino directly, without any level conversion.
Try the SN74LVCC3245, It is very good, has separate supplies for the two halves and is controllable for direction.
For going from a 3.3V CPU r whatever to 5V logic, use a 74HCT logic part and the input will quite reliably be driven by 3.3V logic. I use this trick all the time where we have 3.3V IO on FPGA's and need to interface with 5V peripheral systems.
the easy way, as mentioned above, is to step down 5V signals to 3.3V through a resistor divider.
Going the other way, most 5V logic will recognize 3.3V as a high signal, so you can connect to TTL/CMOS inputs directly.
If you are trying to connect the Xbee cheaply to 5V logic levels, it has been done in the XBee module by Libelium. Why not just look at their open-s source schematic, as posted on the libelium.com web site?
