Be sure to put the videos in the "100ANV01" Folder:
:/MP_Root/100ANV01
After you do that, try to access them directly from the PSP main menu, If it still keep showing "There are no videos", I recommend you to check the videos on an iPod, or any other Mp4 video player, like you've said, just to be sure that the videos are working properly...
If non of this works out, try out to re-formatt the Memory stick, and try to put the videos again, that should do it!
Hope that helps!
