I'm also a newbie here, so maybe there are better solutions:
Two days ago I asked about
making a 2d racing game and how to determine if the car has left the track. I got an advice which may fit to your problem.
How about making a second map with only a few colors?
For example: all land colored brown, deep water colored blue,...
You could than read your current position from this 'shadow map' and determine what kind of underground your actual position has.
Here's the link to my question:http://www.java-gaming.org/cgi-bin/JGNetForums/YaBB.cgi?board=cluebies;action=display;num=1108479531