The best way I found is this, use imTOO Zune Video Converter.
Pick these settings, otherwise it's not going to be full screen:
Explanation:
Full, keeping aspect ratio, assuming your movie is wide screen, just makes it.. wide screen. Making it 4:3 aspect ratio, plus full makes it full screen + wide screen.
It looks a little smudged, but better then not full screen.
I'm going to try 16:9 later to see if it makes it normal full screen.