I've noticed a similar or the same error and have an anecdotal partial solution in a limited number of cases - can you restore whole (Mac) disk image to the disks that otherwise fail to format?  It may be more successful to try doing this from WinImage on a PC if that's an option and depending on what type of disks we're talking about.  (This solution is irrelevant if there's a catastrophic physical problem though)