Eu procurei para verificar se esta pergunta não é dup, vejo que alguns não têm resposta e outros não ajudaram.

este é o meu código:

private void startRecording()
{
            mRecorder = new MediaRecorder();
            mRecorder.setAudioSource(MediaRecorder.AudioSource.MIC);
            mRecorder.setOutputFormat(MediaRecorder.OutputFormat.THREE_GPP);
            mRecorder.setAudioEncoder(MediaRecorder.AudioEncoder.AMR_NB);

            mFileName = Environment.getExternalStorageDirectory().getAbsolutePath();
              mFileName += "/recordedHeckPost_.3gp";

            mRecorder.setOutputFile(mFileName);                  

                try {
                    mRecorder.prepare();
                    //Thread.sleep(2000);
                    mRecorder.start();                  
        }
                catch (InterruptedException e) 
                {   // TODO Auto-generated catch block
            e.printStackTrace();
        }     
            catch(IllegalStateException e)
            {
                e.printStackTrace();
            } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
}

private void stopRecording()
{
        mRecorder.stop();
        mRecorder.release();
        mRecorder = null;
}

Depois de executar este código (no Nexus 5), recebo o início abaixoexceção -38 com falha:

05-31 18:17:39.404: E/MediaRecorder(2464): start failed: -38
05-31 18:17:39.404: W/System.err(2464): java.lang.IllegalStateException
05-31 18:17:39.404: W/System.err(2464):     at android.media.MediaRecorder.start(Native Method)

Obrigado.