Android video recording - IllegalStateException on mediaRecorder.start

I am following the tutorial on https://developer.android.com/guide/topics/media/camera.html#capture-video

As such I follow the below order when trying to start the camera:

1. Camera.open
2. camera.unlock
3. mediaRecorder.setCamera
4. mediaRecorder.setAudioSource
5. mediaRecorder.setVideoSource
6. mediaRecorder.setProfile
7. mediaRecorder.setOutputFile
8. mediaRecorder.prepare
9. mediaRecorder.start <- this is where I get the IllegalStateException

I can figure out what could be going wrong since I'm following the guide, running 5.0.2

private Camera mCamera;
private MediaRecorder mMediaRecorder;

public CameraActivity() {
    mCamera = getCameraInstance();
    mMediaRecorder = new MediaRecorder();
}

public static Camera getCameraInstance(){
    Camera c = null;
    try {
        c = Camera.open();
    }
    catch (Exception e) { ... }
    return c;
}

public void startRecording() {

    mCamera.unlock();
    mMediaRecorder.setCamera(mCamera);

    mMediaRecorder.setAudioSource(MediaRecorder.AudioSource.CAMCORDER);
    mMediaRecorder.setVideoSource(MediaRecorder.VideoSource.CAMERA);
    mMediaRecorder.setProfile(CamcorderProfile.get(CamcorderProfile.QUALITY_LOW));
    mMediaRecorder.setOutputFile(getOutputMediaFile(MEDIA_TYPE_VIDEO).toString());

    try {
        mMediaRecorder.prepare();
    }
    catch (IOException e) { ... }
    catch (IllegalStateException e) { ... }

    try {
        mMediaRecorder.start();
    }
    catch (Exception e) {
        Log.d(TAG, "exception on mediaRecorder.start" + e.toString()); // This is the exception that gets thrown on .start
    }
}

My manifest includes all necessary permissions

<uses-permission android:name="android.permission.CAMERA" />
<uses-permission android:name="android.permission.RECORD_AUDIO" />
<uses-permission android:name="android.permission.RECORD_VIDEO" />
<uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/>

<uses-feature android:name="android.hardware.camera" />
<uses-feature android:name="android.hardware.microphone" />

I have also tried manually setting format instead of using .setProfile, same results

    mMediaRecorder.setOutputFormat(MediaRecorder.OutputFormat.MPEG_4);
    mMediaRecorder.setAudioEncoder(MediaRecorder.AudioEncoder.AAC);
    mMediaRecorder.setVideoEncoder(MediaRecorder.VideoEncoder.DEFAULT);

Update

The file is indeed created, though it's unplayable of course, so I know it's working up to that point. The call to prepare does not throw an exception, and occurs before start. Same exception thrown on start()