Depending on the polygon count of your terrain, it might help to use an OcTree to speed this up...like so:
OcTree oc = new OcTree(terrain.getMesh(), 250, OcTree.MODE_OPTIMIZED);
terrain.setOcTree(oc);
oc.setCollisionUse(true);
oc.setRenderingUse(false);
I had the same problem with my RPG prototype. Without the octree, player (or entity)-terrain collisions are pretty slow. With the octree, it's fine for the player itself. If multiple enemies should be calculated too, it might become a bit too much for current devices. So i added another option that i'm using for enemies only...i sampled the terrain's heights at fixed intervals using calcMinDistance and stored that in a simple (but memory intense) data structure (currently 800*800 samples). This is basically a height map and it's used to calculate an enemy's current height based on the closest samples with some crude interpolation. It's not perfect, but it works good enough IMHO.