Video sometimes doesn't play if the orientation is changed in the script right before calling Handheld.PlayFullScreenMovie. This looks like a racing condition, because it's not reproducible every time. This is reproducible on devices with Ice Cream Sandwich and Jelly Bean Android versions. Not reproducible on Gingerbread devices.

Tested devices:
Samsung Galaxy S with Android 2.3.3 (not reproducible)
Google Galaxy Nexus with Android 4.0.4
Samsung Galaxy S3 with Android 4.1.1

Unity Versions:
4.0.1f2 (9bb580cddf70)
4.2.0a1 (e507cb846753)

A workaround would be to make a dedicated scene for playing the video. In that scene in the "void Start()" method the orientation could be changed to autorotation or landscape. Then in the "void Update()" method the movie could be played by calling Handheld.PlayFullScreenMovie and then when the video ends on the next update the orientation could be changed back to portrait and the previous scene could be loaded.