Pues tendrás que usar la búsqueda para buscar "tutorial para usar la búsqueda" porque referidos a problemas con videos en PSP hay como cientos de post (quiza pasen de los 1000, es posible)
Por decimoquinta millón de vez (esto ya es un tópico), MP4
NO es un formato de video, MP4 es un contenedor, no es más que una manera de unir (muxear) el audio/video/subtítulos dentro de un mismo archivo, es como si metes un MP3 y un TXT dentro de un ZIP y lo llamadas ... Ebook Musical, el formato de ese Ebook Musical no es ZIP porque no son más que un TXT y un MP3, el ZIP solo es la manera de unirlos
Bajate un programa llamado MediaInfo y pasaselo al archivo MP4 para ver en qué formato está el video y el audio, si no es MPEG4 AVC + MP3/AAC y lo estás metiendo en la carpeta VIDEO NO FUNCIONARÁ. Si es MPEG4 ASP (Divx/Xvid) ya lo tienes que meter en otra carpeta diferente
Si es otro formato de video, no te desesperes, muy probablemente jamás te funcionará