That's a native application, you can't really compare that to the performance that you'll get with the Dalvik VM. However, it should be possible to get this reasonable fast even with Dalvik. Giving an advice is difficult, because i've no idea how your level/game/code looks like. But i can give some general hints:
1.) When using calcMinDistance, watch the threshold value. When using "normal" collision detection, watch Config.collideOffset. Choose reasonable values depending on your level but don't use unnecessary high values, as this will slow down the calculations.
2.) set Object3D.setCollisionOptimization(true) on your objects
3.) Consider using an OcTree. By default, the OcTree will be used for rendering AND collision detection. You might want to limit it to collision detection...just see the JavaDOC of the class for more information
4.) Consider to use an alternate collision mesh, i.e. when rendering, you are using a high detailed mesh of the level, but when doing the collision detection, you us a simplified version with less polygons. You can achieve this by switching visiblity of these meshes before and after rendering for example.