When I drop the airstone into water the current goes up to 350mA but the motor stalls. I get the same response when the power source is batteries but the motor doesn't stall

Measure the voltage on the input and output of the LM317 when you're trying to draw 350mA.

What is the nature of the heatsink? The regulator will be dissipating more than 3W and it will go into thermal protection if the heatsink isn't adequate.

I didn't bother looking for specs on your 12V power supply. Can you post the specs? Particularly, current rating and whether DC output is regulated.

 

Here is the schematic
View attachment 86074

I measured the current by putting my meter in series with the supply.

Did you put the current meter in series with the output *AND* the load? - Shunting the output with just the current meter is likely to activate the current limit.