What are the resolution, codec and bitrate of your movies? the best you cna get form mplayer (which is the back end for kino2) is 320x240, MGEP1, MPEG2 or DivX with bitrate at about 300-500 Kb/s.
Also, in kino2 make sure to use Full Screen, overlay, doubel bufer, no scaling and QVGA mode.