Samsung Galaxy SIII mediaRecorder() issues. (Corrupt Video)

Question

I have a problem with the Samsung Galaxy SIII. In the app we are creating, we use a mediaRecorder to record a video of the user using the front camera. I have looked thoroughly in the documentation and all over forums and I have seen a few similar posts for the SII or crashes in general, but those fixes unfortunately did not work for us. The process that the camera records is as follows --> There is a function (code will be provided) that checks each devices compatible camera resolutions, then we check to see if they meet our specifications (right now it is 480p or less) If there is one that meets this criteria then it uses that quality to set the videoSize() (function provided by android to set the recording size of a video). This seems pretty trivial and looks like it would work with almost any device. This code does work for a couple different devices that we've tested it on (e.g. Galaxy S4, and Galaxy Stellar). But for some reason the SIII is being very difficult. When you record on the SIII in any resolution lower than 720p, the video becomes corrupt and plays back with multi colored screen (screen shots in link below). Why not just record the video in 720p+ then? Unfortunately we need lower video sizes so that it is not such a heavy data load to transfer over a cell phone provider network.

So my question is, why does recording corrupt the video in any lower resolution than 720p, when the resolution that it uses is being pulled out from a list of device supported resolutions?

This is the function to pull supported resolutions from the device.

public Camera.Size getSupportedRecordingSizes() {

    Camera.Size result = null;
    Camera.Parameters params = camera.getParameters();
    List<Size> sizes = params.getSupportedPictureSizes();

    for (Size s : sizes) {
        if (s.height < 481 && s.width < 721) {
            if (result == null) {
                result = s;
            } else {
                int resultVideoSize = result.width * result.height;
                int newVideoSize = s.width * s.height;

                if (newVideoSize > resultVideoSize) {
                    result = s;
                }
            }
        }
    }
    if (!sizes.isEmpty() && result == null) {

        Context context = getApplicationContext();
        CharSequence text = "Used default first value";
        int duration = Toast.LENGTH_SHORT;

        Toast toast = Toast.makeText(context, text, duration);
        toast.show();
        for (Size size : sizes) {
            if (result == null) {
                result = size;
            }
            int previousSize = result.width * result.height;
            int newSize = size.width * size.height;
            if (newSize < previousSize) {
                result = size;
            }
        }

    }
    return (result);
}

This is the code for our mediaRecorder (shortened for simplicity)

mediaRecorder = new MediaRecorder(); 
    setCameraDisplayOrientaion();
    //sets devices supported video size less than or equal to 480p (720x480 resolution).
    Camera.Size vidSize = getSupportedRecordingSizes();

    camera.unlock();
    mediaRecorder.setCamera(camera);
    mediaRecorder.setAudioSource(MediaRecorder.AudioSource.MIC);
    mediaRecorder.setVideoSource(MediaRecorder.VideoSource.CAMERA);
    mediaRecorder.setOutputFormat(videoFormat);
    mediaRecorder.setAudioEncoder(audioEncoder);
    mediaRecorder.setVideoEncoder(videoEncoder);
    mediaRecorder.setOutputFile(fullQuestionPath);
    if (vidSize == null) {
        mediaRecorder.setVideoSize(480, 360);
    } else {
        mediaRecorder.setVideoSize(vidSize.width, vidSize.height);
    }
    mediaRecorder.setVideoFrameRate(videoFrameRate);
    mediaRecorder.setPreviewDisplay(surfaceHolder.getSurface());

     //set the bitrate manually if possible.
    if (android.os.Build.VERSION.SDK_INT > 7) {
        mediaRecorder.setVideoEncodingBitRate(videoBitrate);
    }
try {
        mediaRecorder.prepare();
        mediaRecorder.start();
}
catch (Exception e) {
        Log.e(ResponseActivity.class
                .toString(), e.getMessage());
        releaseMediaRecorder();
    }

The images that correlate to this problem are here http://imgur.com/a/8F7Tb (Sorry about not posting earlier.)

The order of these images are as follows --> 1) Before recording, preview is going. 2)Recording, preview showing current recording/recording. 3)Stop Recording, recording has stopped as well as preview. 4) Playback, this is where the issue is, it shows this multicolored corrupt image, which is the same if you pull it from the device directly.

EDIT: Note, I have also tried using the CamcorderProfile and setting the quality to low or high. Setting to QUALITY_HIGH forces 720p which recording works at, but QUALITY_LOW, despite everyone having quite the opposite problem, does not work for me.

EDIT: Anyone have an idea to point me in the right direction?