I tried again with Sonic RecordNow Deluxe and the same thing happened. It seems to correlate with burning on my system, but not Nero specifically. Furthermore, of the 5 DVDs I've burned so far, they are all coasters. Everything seems to write fine, but the verify fails with read errors. Using kprobe, the discs actually look really good, so I'm not sure what's going on.
I'm going to see if restoring my system from an older backup fixes anything. Otherwise, it may be back to the store with this burner.