To Mark Dygert, What is this script called? You mentioned it on a previous reply. "It also doesn't help that your operand mesh is several elements and some are clipping into others which will complicate things. You should probably break off each element (there's a script for that) and treat each one as an operand." Thanks!
The meshes need to be water tight for any type of boolean to work. No open edges, no boarders no double faces, no flipped faces. It also helps if a single element is operating on a single element. If you have multiple meshes joined into one edit poly its going to have trouble. They changed ProBoolean a bit in a 2011…
There are several. Matt Lichy's turbotools include a script to do it, along with other awesome stuff. Plus he's a polycounter so no reason not to try 'em ;-)