Boolean half the time doesn't work but does union? Im not sure if Im doing something wrong here or what is happening but about 50% of the time whenever I do a normal boolean difference modifier, if I have at all modified the big object previously, I get this instead of a nice clean cut - 



Where that bottom cube sticking out was supposed to be cut away. I have no idea what to do about it and oddly a union cuts a hole, but doesn't make the insides have "walls" so to speak. Ive tried recalc normals and everything here How to cut holes in an object using another object?

But nothing is working. What is wrong? its doing an additive boolean.
A Boolean Modifier usually fails for one of two reasons:


Your face normals are pointing in different directions. To the modifier it seems like the mesh doesn't have a clear distinction between inside and outside. Happens often through extrusion. Select all verts and hit CTRLN to recalculate them.
Your mesh isn't watertight. That happens when any edge of your mesh has more (or less) than 2 faces attached to it. Deselect all verts and hit CTRLALTSHIFTM. That'll select most troubling parts. It can be useful  to do this twice, first in Vertex Select Mode, then in Edge Select Mode because the clues from what gets selected are different. If that's the case, recalculating normals won't work either. I usually go paranoid and avoid holes (only one face attached to any edge) as well.