I'm still on 3.40OE and I can confirm that there is no problem with playing videos.
I usually use PSPVideo9 or XviD4PSP to convert the videos. In 320x240 I haven't encountered any problems, but it can be a bit tricky to make 480x272 videos.
Just use the dafault properties of these converter-programs then you should be alright.
Bookmarks