This may be stating the obvious, but make sure that your MIDI input objects in Max have the input port properly defined, with the correct capitalization, spacing, and punctuation:
[ notein "to Max 1" ] not [ notein To MAX1 ]
You can also command-double-click on the object and select the port from the resulting popup menu.
Make sure both Live and Max are open. In Live, in one of your MIDI tracks, click on the "MIDI To" popup menu and choose Configure…, which will open up the MIDI Sync tab of the Live Preferences window. In the lower half of that window you should see "Output: to Max 1" and "Output: to Max 2" as possible ports; if the Track button is Off for those ports, click on those Track buttons to turn Track output On (highlighted). Now when you close the Preferences window and again click on the "MIDI To" popup menu in a MIDI track, those ports should show up as available options.