Also try turning on hidden geometry (View>Hidden Geometry). That will allow you to edit/delete portions of the terrain mesh that shouldn't be there.

My favorite is Stray Lines:

favicon

(www.smustard.com)

It labels all lines that do not meet up with another line, and that is what is going on in your model. Download that, then run it and it will show each little broken spot. You might have to zoom in very very close to see the problem. But once you see the line that is not meeting up, just connect it and it should work.

Though if it is too small, SU will not let you draw it. You'll have to figure out a way around that if it comes up.

Intersection always works in the editing context you are in. So while you were "outside" the terrain group, the intersection lines did not affect it as they were also created outside. Now as you have exploded the terrain, try to intersect again (if there is no volume intersection, select all you want to intersect and intersect with selected).

Turn on hidden geometry and only select the faces in the terrain that should be affected - the time needed will be much less this case.

three 3d converters you may not have tried are
meshlabserver:
similar options to Meshlab from a scrpt i.e. from ruby...
import:PLY, STL, OFF, OBJ, 3DS, COLLADA, PTX, V3D, PTS, APTS, XYZ, GTS, TRI, ASC, X3D, X3DV, VRML, ALN
export:PLY, STL, OFF, OBJ, 3DS, COLLADA, VRML, DXF, GTS, U3D, IDTF, X3D
Point Clouds support.
meshconverter:
Supported input filetpyes: dxf obj off ply stl 3ds wrl (VRML 2.0 only)
Supported output filetypes: dxf js obj off ply stl wrl (VRML 1.0 and 2.0)
assimp:
Supported input filetpyes:
Collada ( .dae )
Blender 3D ( .blend )
3ds Max 3DS ( .3ds )
3ds Max ASE ( .ase )
Wavefront Object ( .obj )
Industry Foundation Classes (IFC/Step) ( .ifc )
XGL ( .xgl,.zgl )
Stanford Polygon Library ( .ply )
*AutoCAD DXF ( .dxf )
LightWave ( .lwo )
LightWave Scene ( .lws )
Modo ( .lxo )
Stereolithography ( .stl )
DirectX X ( .x )
AC3D ( .ac )
Milkshape 3D ( .ms3d )

TrueSpace ( .cob,.scn )
Supported output filetypes:
Collada ( .dae )
Wavefront Object ( .obj )
Stereolithography ( .stl )
Stanford Polygon Library ( .ply )

there are others out there...
john