In my case, the reason this happened was that I stopped the camera prevew, changed the preview resolution, then restarted the preview all while recording. Something that would look like this if you compacted all of the method calls:
camera.startPreview();
camera.unlock();
recorder = new MediaRecorder();
recorder.setCamera(camera);
recorder.setVideoSource(MediaRecorder.VideoSource.DEFAULT);
recorder.setOutputFormat(MediaRecorder.OutputFormat.MPEG_4);
recorder.setVideoFrameRate(24);
recorder.setVideoEncodingBitRate(3000000);
recorder.setVideoEncoder(MediaRecorder.VideoEncoder.H264);
recorder.setOutputFile(output.getAbsolutePath());
recorder.setPreviewDisplay(holder.getSurface());
recorder.prepare();
recorder.start();
camera.stopPreview();
Camera.Parameters cameraParameters = camera.getParameters();
cameraParameters.setPreviewSize(x, y);
camera.setParameters(cameraParameters);
camera.startPreview();
recorder.stop();
recorder.reset();
recorder.release();
recorder = null;
camera.lock();
camera.stopPreview();
In reality, the reason the preview size was being changed after the recording started is complicated and domain specific, so I will save the details. However, the point is the same: you cannot change the preview size without stopping it, but you cannot stop the preview after the media recorder has started. I'm sure there are other things that could cause this, like any other number of camera parameters.
You should be sure to check that the camera is not disturbed while recording a video.