We had the same problem on iOS. Playing the movies from a coroutine and inserting a yield to wait for a second solved the problem.

IEnumerator PlayMovies() {
    iPhoneUtils.PlayMovie("Movie1.mov", Color.black, iPhoneMovieControlMode.CancelOnTouch);
    yield return new WaitForSeconds(1.0f);
    iPhoneUtils.PlayMovie("Movie2.mov", Color.black, iPhoneMovieControlMode.CancelOnTouch);
}