Welcome to the forum
Shouldn't matter one bit what type (CD-R, RW) of disc you use, as long as there's enough space on the disc you should be good to go.
What program are you using? Only time I ever saw that kind of message with a fresh blank disc, has been when certain other programs are installed. So, do you have Daemon Tools/Alcohol/PowerISO or anything similar installed?
If you do, don't do anything (like uninstalling them) for the minute, as with Acohol/Daemon Tools at least, there are a couple of settings changes which could fix it.
Something else I'll ask, is does the drive read burned or pressed CD media OK?
EDIT: How much you can fit onto a CD will depend on whether you are burning it as a data disc (i.e. as .mp3, .wav etc if your player supports those data formats), or as a regular audio CD. If burning as .cda (regular audio, like a pressed music CD), it should say on the disc packaging how much you can fit on - something like 70 minutes, 80 minutes etc.