El archivo de vídeo no se puede reproducir

Hay una serie de factores que determinan si un vídeo se reproducirá en Android:

1. Tiene que ser el códec correcto - Ver esta lista
2. Tiene que ser lo suficientemente pequeño como para descargarlo por completo antes de reproducirlo o estar codificado de una forma que permita el streaming.

Lo más probable es que el problema que veas sea que el códec con el que están codificados los vídeos no es compatible, así que sí, recodifica con ffmpeg o mencoder o algo similar en uno de los códecs de vídeo compatibles puede funcionar.

Para habilitar el streaming, si primero lo codificas como un archivo MP4 y luego lo pasas por algo como MP4Box lo etiquetará para el streaming para que puedas reproducir videoclips más largos en Android.