You need to make an Aux input in PT, select the insert "Instrument->Max/MSP", the make the Aux track's output go to a Bus. Then create an audio track, select the Bus as its input, and then you can record.
This comes up quite frequently, and let me first re-assure you that it is possible, but yes, it can be a pig.
If you search the forum, there are quite a few useful suggestionss, but first and foremost, I would try re-installing ReWire - trash your /Library/Application Support/ReWire folder first, then re-install.
Also, the order in which you do things is important i.e.
1. Launch the host (Pro Tools).
2. Launch MaxMSP and select ‘ad-rewire’ as the audio driver.
3. Switch on the DSP; if there were any problems making the connection, a message would appear in the Max window.
4. In Pro Tools, create a new audio (or instrument) track, and select the input as ‘MaxMSP.
5. To record the audio to Pro Tools, send the audio track to a bus, then create a new stereo audio track and select that bus as it's input. Bring the level up with the bus send, and record onto the new track.
If all else fails, the latest version of Jack (www.jackosx.com) is supposed to work with PT 9, but so far I've not been able to get it working without PT complaining of CPU overload,