Since no one's mentioned it, songs purchased from the iTunes Music Store aren't really CD's, they're already in a compressed format (Apples AAC format, which is comparable to MP3 but gives somewhat better fidelity relative to the file size). These files are compatible with any iPod and don't require any conversion. Not only would there be no advantage to converting them to MP3, you'd suffer a slight quality loss.
Forgive me for asking, but did you buy CD's (physical disks) or digital downloads, and if you bought downloads are you sure you bought them from the iTunes Music Store and not some other on-line source?
Generally, if you buy physical CD's and rip them yourself they won't be DRM-protected (regardless of what you used to rip them), though they may ripped into a format that's not compatible with some players. If you bought digital downloads they may be DRM-protected in such a way that the music can only be used on equipment that's compatible with that particular seller's DRM scheme, or they may be compressed using a format that's only compatible with certain software or players.
Besides DRM issues, there has been a little bit of a 'format war', similar to the old VHS/Beta or HD-DVD/Blu-Ray battles, in the digital music download arena regarding compression formats. MP3 is essentially a 'universal' compression format that any digital media player should be able to play. WMA is Windows' proprietary format, as AAC is Apple's proprietary format. Apple's format, as used on the ITMS, should be compatible with any Apple products, e.g. iTunes (on any computer), or any iPod. I should probably point out here that WMA files are not MP3 files. Some on-line sources other than the ITMS sell their stuff in WMA format, which is not directly compatible with Apple's stuff. I think Wal*Mart and maybe Amazon did that. I believe there are methods of converting WMA files to Apple-compatible formats, but I'm not sure that iTunes can do it. I'm almost certain it won't be able to do it if the WMA file is DRM-protected. There may be third party software that can do this for you though.
In short, if you have AAC files from the ITMS you shouldn't have any troubles with them with either iTunes or your iPod. The same thing goes for actual MP3 files. WMA files will not be directly compatible, especially if they're DRM-protected. I don't have a lot of experience dealing with such files, so others may be able to help you out there.
I'm sorry you're having troubles. Like a lot of people here, I use iTunes exclusively and find that it works very, very well. It sounds like your existing music library is a little bit of a hodge-podge, and may take some cleaning up to run smoothly.
. As I suspected you had WMA files and THAT is what needs converting. iPods will not play WMA files, so you will either have to let iTunes convert a few at a time or re-rip. There is no way to get an iPod Touch to play WMA files.