If you just say "320x240" to Ubuntu, you'll get 320x240 doublescanned. That is, each line will be scanned twice. Either that or you'll get it at 120Hz refresh. Either way, the horizontal sync is 30kHz (VGA compatible), so a TV won't like it. They do this because that's what you have to do for a PC.
Chances are, you won't be able to get X to do what you want without manually hacking the config file. This is just not something 99.9% of users have any need for. Fortunately, xorg.conf is pretty straightforward. Tell it that your monitor has a horizontal scanrate range of 14.5-16kHz, and hopefully it'll remove the doublescan option from 320x240 for you. Heck, it may automatically decide to interlace 640x480 for you. If it doesn't, you'll have to use a modeline. Fortunately, others have compiled a ready-made
list of modelines for this.
I recommend this modeline:
ModeLine "ATSC-480-59.94i" 11.958 640 664 736 760 480 484 492 525 Interlace
That gives you 640x480 at timings that should display properly on any NTSC television (though there will be some overscan).
For an SDTV, you *WILL* have to deal with interlaced output at 640x480. That's all the TV can do. No way around it. You'd need an "EDTV" to handle 640x480 progressive.
I have long suspected that the reason these DVI/VGA-to-component dongles only work on certain hardware is that there is driver trickery involved. I'm guessing that the card is asked to convert colorspaces internally (something the hardware is very good at doing) then output YPbPr for you. The dongle just changes the connectors around. Your experiences seem to confirm this, at least for the dongle you're using.
I have had excellent luck using various methods of getting the PC to output suitably timed video (custom modelines in Linux, driver tricks/soft15k-like utilities in windows, etc.) and hooking the output up to a RGB-to-SVideo adapter I built. You can buy such adapters pretty cheap from places like arcademvs.com. Quality isn't quite as good as component, but unless you were to place the two side-by-side, you'd never be able to tell (and even then you'd probably have difficulty).