Can't do subtraction with Boolean modifier
Your mesh has to be non-manifold. I had troubles with this as well. Removing doubles it typically a good way to start achieving non-manifoldness. There are enough tutorials out there and somewhere in the documentation there's a hint, that your volume has to be non-manifold for the boolean stuff to work properly.