I've had that before and it seems it was usually that I didn't have them aligned like I thought I did. One was slightly off-plane or something. Or the overlap wasn't actually what I envisioned it being, so there was the situation where the subracting face came out of contact with the other body. I've gotten to where, if possible, I make the solid which will subtracted from the main object longer/wider than necessary, since it goes away anyhow.
For instance, for the simple case of having a 6" dia X 12" L cylinder that I want to make a 2" dia hole through, (a the centerline, quadrant to quadrant, perpendicular to the axis), if you make a 2" dia X 6" L cylinder to do the subtraction with, you might get that error. But if you use an 8" L X 2" dia cylinder and let it stick out on either side, you won't.
Other times, I've had a drawing error where a face wasn't exactly as I meant for it to be.