When doing booleans you have to be very carefull that you know exactly what you are doing, firstoff make sure the normals are the right way around (if even one is the worng way youll be screwed, use normals conform). Make sure no non manifols surfaces (some of the non manifolds get fixed by the provious step) exsist etc...
And offcourse this is for poly booleans only... Nurbs booleans are a total other ballgame...
Also make sure there isnt any coplanar surfaces anywhare (eg if you try to subtract a 1 lengt sylinder rom a 1*1*1 cube so that the ends are exactly on the same spot youll be at the mercy of the processors floating point accuracy)
Also cleanup isnt necceserily enough to make the sufficent changes... Since it doesent take into acount that you might have a number of different shells on the surface in question this confuses maya very much (atleast in poly booleans), so make sure your vertices are actualy merged. Same goes to Nurbs except maya allows you to do this as long as you use the group(s) (a nurbs cube is a group of 6 surfaces), instead of individual surfs, but be avare that this can be a mathematical horror at time s so not everything is doable.
Multible booleans many times mess things up a bit.
But i must say once i understud how they work only NURBS booleans some times cause some probs for me, anymore... but maybe thats expected since even very hardcore solid apps (like Catia, ideas and Pro/E) fail t the same nurbs stuff so....
Oh by the way i tried using a primitive cube and deleted some 50 different poly cylinders from it (with history intact), and they all worked fine...