I haven't looked into it specifically (I don't use rhythmbox), but I suspect this is an issue that has emerged due to a patent dispute. Rhythmbox is a front-end for several standard tools, and one of those was changed recently, removing one of the audio encoding elements that would be used for this because one of those vulture companies that only exists to collect IP patents laid a claim to it and started threatening law suits.
Anyway, according to the forums, GnomeBaker seems to be the standard CD writing utility for Ubuntu. There also seems to be one called Brasero.
I use something called kb3, but it's a native KDE app, and you'd need to install a bunch of other crap to get it to work. (KDE is a desktop manager. Ubuntu using Gnome standard. Kubuntu is Ubuntu with KDE, just FYI.)
Here's a thread:
http://www.ubuntugeek.com/how-to-burn-a-cdsdvds-in-ubuntu-linux.htmlOnEdit: It's Brasero I was thinking of. I'm not up on the standard Ubuntu apps.
Do you have Brasero installed? Apparently Rhythmbox now does burns by going through Brasero. I dunno for sure. If you can't figure it out easily via that link, let me know, and I'll look into it and figure out at home precisely what needs to be done.