I had a problem yesterday where Rhythmbox wouldn't rip a CD to .m4a format. I went to the Preferences window to set the format, and it wouldn't appear in the drop-down. Curiously, if I clicked the Add button it would show the existing formats, and .m4a was in that list.
After much flailing, I discovered that you need to have both gstreamer0.10-plugins-bad and gstreamer0.10-plugins-bad-multiverse installed. I had removed the multiverse one a few weeks ago when I thought I was cleaning up after a previous round of flailing to get something around music working.