Just for you to consider before getting in too deep:
Always check the simplest things (and/or cheapest) first.
Have you burned to this brand AND type of disk before (eg., same brand but different type, say... Single Layer vs. Double Layer)? Your burner, for instance, will burn DVD-RW/+RW, but not in double layer.
Have you cleaned the drive lately? Burners are notorious for problems burning DVD's if the drive is the least bit dirty.
Are you using a new kernel? A drive that functions perfectly under a previous kernel, may have certain issues under the newer kernel.
Have you tried a less sophisticated burning program than K3b? Sometimes K3b is just too smart for its own good.
Have you tried to burn another disk from the same batch to see if you get a different result? Sometimes an unused disk is defective to begin with.
Is your current istallation free of glitches/corruptions? Certain flaws may only appear in very specific situations.
If none of these approaches solves the issue, then its time to consider the possibility that the drive is in the early stages of failure, where most of the functions/media work, but certain function/media no longer do. This is especially true for older drives (2+ years).
May all of your troubles be easily solved,