Supongo que los videos deben de estar con el formato adecuado para que los lea el cel, puedes probar convertirlos al formato 3gp, con algún software que sea dedicado a realizar ese tipo de operaciones.

Saludos.