lilith, it would be interesting to encode the same video with lower bitrate (~300) and a horizontal resolution of <=400px. This way you can find out if the video is simply too demanding in terms of CPU power or if it's something else.

Also, check http://wiki.maemo.org/Manual_video_encoding