Problem playing videos on certain Android devices

I am trying to play a video using Easy Movie Texture, but it doesn't word on some devices, while others can play it just fine.

Here is the adb logcat output I get:

 --------- beginning of system
 --------- beginning of main
 E/Unity   (26338): Unable to find AudioPluginOculusSpatializer
 D/Unity   (26338): GL_EXT_debug_marker GL_OES_texture_npot GL_OES_compressed_ETC1_RGB8_texture GL_OES_standard_derivatives GL_OES_EGL_image GL_OES_depth24 GL_ARM_rgba8 GL_ARM_mali_shader_binary GL_OES
 _depth_texture GL_OES_packed_depth_stencil GL_EXT_texture_format_BGRA8888 GL_OES_vertex_half_float GL_EXT_blend_minmax GL_OES_EGL_image_external GL_OES_EGL_sync GL_OES_rgb8_rgba8 GL_EXT_multisampled_r
 ender_to_texture GL_EXT_discard_framebuffer GL_OES_get_program_binary GL_ARM_mali_program_binary GL_EXT_shader_texture_lod GL_EXT_robustness GL_OES_depth_texture_cube_map GL_KHR_debug
 W/Unity   (26338): OnLevelWasLoaded was found on Cardboard
 W/Unity   (26338): This message has been deprecated and will be removed in a later version of Unity.
 W/Unity   (26338): Add a delegate to SceneManager.sceneLoaded instead to get notifications after scene loading has completed
 W/Unity   (26338):
 W/Unity   (26338): (Filename:  Line: 382)
 W/Unity   (26338):
 D/Unity   (26338): #version 100
 D/Unity   (26338): #extension GL_EXT_frag_depth : enable
 D/Unity   (26338): precision mediump float;
 D/Unity   (26338): uniform highp vec4 _ProjectionParams;
 D/Unity   (26338): uniform highp vec4 _ZBufferParams;
 D/Unity   (26338): uniform highp mat4 unity_CameraToWorld;
 D/Unity   (26338): uniform highp mat4 _NonJitteredVP;
 D/Unity   (26338): uniform highp mat4 _PreviousVP;
 D/Unity   (26338): uniform highp sampler2D _CameraDepthTexture;
 D/Unity   (26338): varying highp vec2 xlv_TEXCOORD0;
 D/Unity   (26338): varying highp vec3 xlv_TEXCOORD1;
 D/Unity   (26338): void main ()
 D/Unity   (26338): {
 D/Unity   (26338):   highp vec4 tmpvar_1;
 D/Unity   (26338):   tmpvar_1 = texture2D (_CameraDepthTexture, xlv_TEXCOORD0);
 D/Unity   (26338):   mediump vec2 tmpvar_2;
 D/Unity   (26338):   highp vec4 tmpvar_3;
 D/Unity   (26338):   tmpvar_3.w = 1.0;
 D/Unity   (26338):   tmpvar_3.xyz = ((xlv_TEXCOORD1 * (_ProjectionParams.z / xlv_TEXCOORD1.z)) * (1.0/((
 D/Unity   (26338):     (_ZBufferParams.x * tmpvar_1.x)
 D/Unity   (26338):    + _ZBufferParams.y))));
 D/Unity   (26338):   highp vec4 tmpvar_4;
 D/Unity   (26338):   tmpvar_4 = (unity_CameraToWorld * tmpvar_3);
 D/Unity   (26338):   highp vec4 tmpvar_5;
 D/Unity   (26338):   tmpvar_5 = (_PreviousVP * tmpvar_4);
 D/Unity   (26338):   highp vec4 tmpvar_6;
 D/Unity   (26338):   tmpvar_6 = (_NonJitteredVP * tmpvar_4);
 D/Unity   (26338):   highp vec2 tmpvar_7;
 D/Unity   (26338):   tmpvar_7 = (((tmpvar_5.xy / tmpvar_5.w) + 1.0) / 2.0);
 D/Unity   (26338):   highp vec2 tmpvar_8;
 D/Unity   (26338):   tmpvar_8 = (((tmpvar_6.xy / tmpvar_6.w) + 1.0) / 2.0);
 D/Unity   (26338):   tmpvar_2 = (tmpvar_8 - tmpvar_7);
 D/Unity   (26338):   mediump vec4 tmpvar_9;
 D/Unity   (26338):   tmpvar_9.zw = vec2(0.0, 1.0);
 D/Unity   (26338):   tmpvar_9.xy = tmpvar_2;
 D/Unity   (26338):   gl_FragDepthEXT = tmpvar_1.x;
 D/Unity   (26338):   gl_FragData[0] = tmpvar_9;
 D/Unity   (26338): }
 D/Unity   (26338): fragment evaluation shader
 I/Unity   (26338): ApplicationPause : False
 I/Unity   (26338):
 I/Unity   (26338): (Filename: ./artifacts/generated/common/runtime/DebugBindings.gen.cpp Line: 51)
 I/Unity   (26338):
 I/Unity   (26338): ResizeTexture 0 0
 I/Unity   (26338):
 I/Unity   (26338): (Filename: ./artifacts/generated/common/runtime/DebugBindings.gen.cpp Line: 51)

It worked on every device I tested when I changed the video resolution to a very low resolution, but that won't solve my problem, because the quality looks very bad :(

I tried changing the Graphics API to OpenGLES2 only, but it doesn't solve the problem. I have also tried using the new Unity VideoPlayer instead of Easy Movie Texture, but the problem remains the same.

I appreciate any help on how to proceed!