If you have tried copying the file to the correct directory and named it correctly as listed by Chilly Willy then they should play if they have been encoded specifically for the PSP (Ipod video etc wont work if you just copy them over).
Try naming the file M4V10000.MP4 and placing it in X:\MP_ROOT\100MNV01 (X being the drive letter of your PSP).
If that doesnt work then rename it MAQ10000.MP4 and place it in X:\MP_ROOT\100ANV01
If the video still wouldn't play, it probably isnt encoded correctly for the PSP. Try re-encoding the video with PSPVideo9.
Here is a guide on how to do that.