GOD!!! This is really weird. (I wasnt joking
The only final reason I can come up with for this to happen is that the cd is screwed up. Try a new cd if you can. (Are you using a CD-RW?)
I also noticed this
cdrecord: Drive needs to reload the media to return to proper status.
Only put the cd in just before you run cdrecord.
Also check if you are running the program Autorun.
then from the output find the pid of Autorun, and kill it.
Then run cdrecord.
If you still get the problem. I would gladly suggest you to give a try with K3B.
Its the best cdwriting frontend ever.
Let me know of your progress