Until we've got a decent mplayer for the C3000, you can try the method below (maybe it's not ideal, but it works for me)
To get mplayer-w100 (1.0pre5.2-1) to play fullscreen on the C3K I just use opie-embeddedkonsole (1.5.9-2) which will start in low-res (at least on my machine). From there I play the movie with "mplayer -fs -vo fbdev -vf rotate=1 -framedrop". Sometimes I have to add "-delay -0.5" because the sound is out of sync for some reason.
Encode example:
"mencoder <Input> -vf dsize=640:272,scale=320:136,expand=0:-104 -sws 2 -o Output.avi -oac mp3lame -lameopts preset=96:mode=0:vol=10 -ovc lavc -lavcopts vcodec=mpeg4:vhq:v4mv:mbd=2:trell:cmp=3:subcmp=3:mbcmp=3:vbitrate=200:autoaspect -ofps 23.976"
Use your original resolution for "dsize" and (<target y resolution> - 240) for the y value of "expand", i.e. (136-240)=-104 in the example above. This will add a border which is necessary because otherwise you can see the (ugly) grey terminal background.
Cheers,
Ben