Now, when you say that "no i am not converting them into that resolution/size i have checked this", what do you mean by that? Are you not converting it 320 pixels by 240 pixels? Also, when you're synchronizing your device, do you have to wait a while before videos are added to it?
That's just how the device is; it'll stretch the video to fit the screen. Unfortunately, that means that it'll make some videos look bad. Try changing to options in your converter program. That's the only solution that I can think of.

|