Not being an i-pod owner or user, I can't give a definite answer but have you tried Super?
It's free and does work with a lot of formats. It's a large download (and rather slow) but I use it a lot even though I do have some cheap converters I have paid for. Ultra mp4 converter is quite stable (free lifetime upgrades as well) and is the one I use for converting flv files (as found on Youtube) to avi for burning to disc (even though it's really made for converting stuff to mp4).
Whatever you use, make sure you keep it up to date.
As I say, I don't have an i-pod so this is best guess.
