Disappearing terrain patches

I think I've found the source of the culling issues I've been seeing.

When I generate the quad tree I'm not sure what bounding volumes to assign to the non-leaf nodes. Since the max Y and min Y are unknown I'm just setting them to +/- max float. This means that the bounding volume is enlarged on Y but centered around 0,0,0. I figured as long as x and z were correct this was acceptable. The mesh patch is fully contained in the AABB or sphere (depending on the setup) so theoretically this should work.

Is it possible this Y discrepancy is causing patches to be out of the frustum compared to the top and bottom planes of the frustum when they really should be inside? If this is true then this explains why some patches flicker in and out at times. Essentially if one large bounding volume is out then all of it's children are also assumed to be out. So if the first test fails incorrectly, the entire branch fails.

Has anyone else had problems with frustum culling via AABB's or sphere's? I do not have this problem in my other renderer which is going to be used for the 'space' portion of the game. The terrain portion suffers greatly from the 'imprecision' of the culling.