Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Given your hardware lists a Vaio I presume you're running window$. If so you can always try Videora which will convert most window$ video file formats to iphone/ipod format.

If using os x then you could always use Quicktime Pro and export the video in the correct format.
 
Use iPodMe. It's free, only 3.9Mb and supports any video format your computer can read natively. It also supports soft subtitles - subs you can switch on or off via the iPhone itself. No other converter does that.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.