I found that my problem was definitely related to burn speeds, but it was that I was burning at too slow of a speed rather then too fast.
I had recently run out of a batch of CD-R media (IBM discs rated at 1-12x) that I had for about the past two years, and purchased newer media without paying too close attention to the specs for the media on the case, which clearly indicated at 48x.
Without thinking I used the same burn command previously used with the older media to produce the faulty discs mentioned in my post:
cdrecord -v -eject speed=4 dev=0,0,0 <ISO_IMAGE_NAME>
All that was necessary to produce discs that booted and passed the media check successfully in all my systems was:
cdrecord -v -eject speed=32 dev=0,0,0 <ISO_IMAGE_NAME>
(My CD-RW has max write speed of 32)
So to cut to the chase, the problem had nothing to do with Fedora and everything to do with me not paying attention to the speed I was burning at.
The one useful thing for me at least, was that I discovered two good sources of information on CD-RW, and burning:
The CD-R primer at: http://www.mrichter.com/cdr/primer/primer.htm
the CD-R FAQ at: http://www.cdrfaq.org/