MainStage can only run as rewire master.
So you could route audio from Max to MainStage but not the opposite.

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.