You say you updated your firmware and videos stopped working, thats really strange.
On firmware 2.80 and below videos had to be placed in <psp's drive letter>:\MP_ROOT\100ANV01 (for AVC encoded video) or <psp's drive letter>:\MP_ROOT\100MNV01 (for MP4-SP encoded video). From firmware 2.81 and above you can just put them in <psp's drive letter>:\VIDEO
Having said that I was under the impression the psp would still playback video from the older directories also.
If you have updated to firmware 2.81 or above I guess its worth trying copying the videos to the newer directory.
My psp is running firmware 1.5, but through the use of a program called devhook i am able top load up newer firmwares into memory, allowing me to play newer UMD games and use all the features of the newer firmwares without having to install them. When I turn my psp off and back on I'm back to firmware 1.5, with its ability to run unsigned code (through a 'security flaw' people have found a way to run all sorts of homebrew games/applications such as emulators for other game systems.
If you had downgraded your psp (no firmware higher than 2.71 can currently be downgraded, there could be a new development in this area quite soon however) I could understand the error as AVC playback was introduced in firmware 2.0.
I'm not 100% sure but I think Lanacane is referring to downgrading, however its not as simple as deleting the old one and re-installing the old. Sony does not want people to downgrade as the main reason for all the firmware updates is to try to block people running anything other than official sony programs on the PSP.
Theres some more info on the subject in my earlier posts
Here.