Make sure you're using good quality cd-r's, blank cd's have gotten cheaper and cheaper over the years, but it's mainly because manufacturers have figured out how to make crappier and crappier media, the good quality more expensive media still exists.
Before you spring for new media, tho, try using nero if you're not already, there's a free demo at
http://www.ahead.de make sure you burn the disc with disc-at-once recording, which automatically closes the disc, and try burning the disc at a low recording speed, i was always skeptical about it, but recording speed really does make a big difference with a lot of drives, unless you have a plextor with the varirec and smartrec and all those crazy recording algorythms.
And lasty, x2 on making sure you use a compatable file type. Make sure they're mp3 format, that they don't use variable bit-rates (even players that are compatible sometimes have trouble, best to avoid it altogether) and the bitrate is compatible with the deck. You should have no problem with 128-192 bitrates for sure. Also, if you've got a few spare discs around, experiment with splitting the files up into more folders, seperate folders for each album, etc. But do not put folders inside of folders, make sure all folders are only 1 deep, head units have trouble dealing with folders inside of folders, and complex file structures. And lasty, how many files are you recording on each cd? If you use really low bitrate files, it may be possible to fit more files onto the cd than the head unit can deal with. I don't know for sure, but it's possible that the unit can only deal with, say 150 or 200 files per disc. Try burning a cd with only a few songs and see if it that one's a desire.
Good luck, there's lots of variables for compressing music, and for burning cd's, so it's difficult for me to help you 100%, but install a fresh cd-recording program in case you screwed up some wacky setting somewhere, and download some pre-encoded mp3's from realmofexcursion.com 's downloads section, so you know whether or not it's your encoding settings.
One last thing i thought of, is make sure the files aren't digital rights management (drm) protected, copywrited files that can only be played on the computer, your computer will allow them to be recorded to the cd as data, but will not open on your player.
Let me know what works. Peace.
Edit: lots of posts while i was distracted with my response, too lazy to leaf through and remove what's already said.