With the newest patch (5.6.3p2) android video appears to no longer play at all.

This same issue occurs for me even with Multithreaded Rendering turned off, FYI, so I don't think that is necessarily the cause.

More Information!
Disabling Multithreaded Rendering option avoided the seriously stuttering, but the video playback frame rate is still very low (lower than 10fps rated by eye). But, again, Pressing the HOME button to return to the launcher desktop, and then switch back to the unity application, the playing frame rate back to normal ( 30 fps looks like), with Multithreaded Rendering disabled.
The major problem maybe what happened to the Android player when lost and regain the foreground, for the video player. Hoping useful for your developers. And waiting for a fix ASAP.

More Information!
I tested playing a mp4 file without audio track, but the issue still existed.
Other thing I find is whether the video player is playing or not, if I press the HOME button to return to the launcher desktop, then switch back to the unity application, the issue disappeared, video playing smoothly until change to another scene. Every time the playing got stutter, return HOME and back the game, the playing recovery smooth.

My 5.6.3p1 also get this problem.
It seems to be audio decoder recretated nearly each second.
Logcat like this:
08-25 00:13:46.112: I/OMXClient(26110): MuxOMX ctor
08-25 00:13:46.118: I/ACodec(26110): Successfully allocate component [OMX.google.aac.decoder]
08-25 00:13:47.089: I/OMXClient(26110): MuxOMX ctor
08-25 00:13:47.096: I/ACodec(26110): Successfully allocate component [OMX.google.aac.decoder]
08-25 00:13:48.085: I/OMXClient(26110): MuxOMX ctor
08-25 00:13:48.092: I/ACodec(26110): Successfully allocate component [OMX.google.aac.decoder]
08-25 00:13:49.083: I/OMXClient(26110): MuxOMX ctor
08-25 00:13:49.091: I/ACodec(26110): Successfully allocate component [OMX.google.aac.decoder]
08-25 00:13:50.095: I/OMXClient(26110): MuxOMX ctor
08-25 00:13:50.103: I/ACodec(26110): Successfully allocate component [OMX.google.aac.decoder]
08-25 00:13:51.108: I/OMXClient(26110): MuxOMX ctor
08-25 00:13:51.114: I/ACodec(26110): Successfully allocate component [OMX.google.aac.decoder]
08-25 00:13:52.095: I/OMXClient(26110): MuxOMX ctor
08-25 00:13:52.101: I/ACodec(26110): Successfully allocate component [OMX.google.aac.decoder]
08-25 00:13:53.040: I/OMXClient(26110): MuxOMX ctor
08-25 00:13:53.048: I/ACodec(26110): Successfully allocate component [OMX.google.aac.decoder]
....

each time it puts a "MuxOMX ctor..." log, the playing back get stutter

Hoping to see this fixed asap as this is causing major issues with a client.

I'm experiencing the same issue with Unity 2017.1.0p4 and 2017.2.0b8, but only with high resolution, high framerate videos. The videos I used to triggered the problem were 3840x1920 at 50fps. It should be noted that the EasyMovieTexture plugin available on the asset store is able to handle these videos without the same symptoms.

I'm having the same issue, Unity 5.6.3p1, really poor performance when I push playback

I also have this problem, video playback is stuttering. S8, GearVR. 2017.1.0f3. Will attempt to revert to 5.6.1p1

Im having the same issue with Unity iOS 2017.1

5.6.1 has no VideoPlayer playback stutter issues.