I finally got my hands on some Taiyo Yudens from Newegg. I also switched my laser with a newer v.5 laser.
I am proud to say burning at 8x on Pioneer DVR-109 works like a charm. All my backups play flawlessly now. I believe it was mostly the media, so if I have learned one thing it is this... DO NOT buy cheap media, only go for top of the notch media.
Thanks everyone that replied... It really helped.