I don't normally recommend running windows programs through Wine, but in this case i've made an exception.
With so many complaints about native cd burners, and even with Nero Linux not working in 11.10 64bit anymore, I thought i'd give imgburn a try through Wine. The 22.214.171.124 version from here:
Just installs and runs without any tweaking whatsoever, and the results are A1.
Well worth a try if you have issues.
I'm a happy burner again
ps. The Wine version i'm using is 1.3.36