There are CD-R, CD+R and CD-RW disks. Generally CD-R disks are the most compatible and CD-RW are the least compatible. I'd get a small pack of name brand CD-R disks and try them to see if that solves your problem. Sony, Memorex, Verbatim, Philips etc.
Edit: I might be crazy and the +R might only be with writeable DVDs. That being said CD-R will still be compatible with more devices than CD-RW.