I have a very similar problem, i have one large cylinder with one set of extruded faces. i then have 9 smaller cylinders around the circumference of the large cylinder and i want to create notches in the large cylinder.

there is no non manifold geometry as i have done clean up and it says nothing to clean up. the cylinders are closed mesh since they are default poly cylinders and i have conformed the normals and tried to do the booleans with different normal directions?

that else can be wrong? iv also deleted the history of the objects.

the 9 cylinders are grouped

cheers
robin