Have you started using a different brand of disc? Not all DVD- and CD-Rs are the same.
As for me, I started getting this error (and also HARDWARE ERROR instead of MEDIUM ERROR) about six months ago while using the same DVD-Rs I'd been using for months.
I don't know if something has changed in OS X (and stayed there during an upgrade to Leopard) or Toast, but I started generating dozens and dozens of coasters when previously I'd made one or two. Maybe my SuperDrive is on the fritz, or maybe it just got more finicky.