Hmm, been too long since I read it so it may not be a specific weakness of Cthulhu's, so much as it is some weird property of the ocean itself blocking his and maybe other old whatsits powers.
No idea what the one primal mystery thing is but, somehow water beats psychic in Cthulhumon. Although he was actually trapped behind a big door the sailors accidentally opened, unintentionally accomplishing his cult's goal of freeing him. And then he got steamboat'd in the face which apparently knocked him out and he got dragged back down by Ryleh sinking again. There's got to be something about water that kept him from just swimming back up, right? Dunno what else would've kept him down.