Terrain collision was a little harder than I thought it would be. This is owing to the fact that the terrain is a concave body, and many contacts are possible with a single sphere and the terrain. Contrast this with two convex bodies (which many physics engines use exclusively) where only a single contact point is possible, and that point is also the closest point between the two objects.
Anyways, terrain-sphere collision works now, and the new terrain engine is integrated into the game. Simulating 400 spheres on the PC takes only ~3ms per update (single threaded). This should make 400 spheres viable on the XBOX 360, which will have about 33ms per update on a CPU core dedicated to physics. This is about a 5-10x speed increase over the performace I was seeing with the default BEPU physics setup.