It's the width, dude. A C4 transmission usually isn't a worry, but a fat mama AOD? Yeah, trust me, most full-length headers are NOT going to fit. I found this out the hard way, too.
There is always kooks headers. They are custom made and cost an arm and a leg, but they fit and they work. While I don't personally have a set (I wussied out and went with shortie headers), I've heard the quality is excellent. Google it to get the web site URL.
BTW, the part where the interference occurs is right at the height where the pan is. On my installation, the collectors bumped up into the sides of the pan. Since I'm both lazy and reluctant to cut & weld tubing, I just borrowed a friend's shorties. FWIW, it's not like there's a HUGE difference between the two, anyway. Best of all, your HEGO sensors will be right where they were intended to be, instead of another ten inches downstream. Read that as: better mileage, power, and a/f control.
