Open the "mixer" application (in your case MainStage) before opening the "synth" application (in your case Max). You presumably got the error message you did because there was no ReWire-capable "mixer" application running at the time.
It works for me (Max 6.1.7, MainStage 3.0.3, OS X 10.8.5), but there are some conditions that can cause the error message you're getting, so...
Make sure that, before you even open Max, you:
1) open MainStage,
2) in the MainStage Preferences... in the Audio tab, ensure that Enable ReWire Host Support is checked,
3) create an External Instrument track, and select Max - RW:Max 6 1/2 as the input
4) in the Finder, select the Max application, choose Get Info... from the File menu, and ensure that Open in 32-bit Mode is NOT checked.
Now, open Max, look in the Audio Status... window, and choose ad_rewire as the Driver. N.B.: If ad_rewire is already the selected Driver, try choosing another Driver such as Core Audio, then re-select ad_rewire.