I had the same problem and found out what was up. The Linux kernel v2.6 doesn't need the old SCSI emulation cdrecord used to use. For instance, if you want to see what your CD device is, use:

cdrecord dev=ATAPI: -scanbus

Then use that device to work with your CDR or CDRW. For mine, it found my CDRW on ATAPI:0,0,0 and to quickly BLANK a CDRW I used this:

cdrecord dev=ATAPIi:0,0,0 blank=fast

Another thing you can do is to put the following lines to your /etc/default/cdrecord file( my CDRW is on dev 0,0,0 ):

CDR_DEVICE=cdrw
# name = ATAPI:yourdev speed(-1 for default) fifosize(-1 for default )
cdrw=ATAPI:0,0,0 24 30m


Now, you won't have to specify the device each time you use cdrecord, it'll use the device specified in your /etc/default/cdrecord file.

note: K3b still doesn't work unless you start it from a commandline as ROOT. I tried "dpkg-reconfigure cdrecord" to set the SUID bit on cdrecord but that still didn't work.