¿Que programa usas para encodear en mp4? prueba con el mediacoder, baja el bitrate, y mira a ver si esta bien puesta la resolucion para el movil, y si los videos van en la tarjeta de memoria comprueba la velocidad de esta, que puede ser una mierda.
Offtopic: No es por meterme, pero: ¿pa que coño t has comprado un "iclone" chino, hay por ejemplo htcs tactiles mas fiables a mejor precio, es que conozco a gente que tiene clones chinos de ipod y tienen un huevo de problemas, y las baterias se joden enseguida.