My guess is non-manifold solid geometry.
First, you do want the inter-part copy to be surface geometry. if it wasn't, then the solids would join into a single part and you wouldn't have any surfaces (or body geometry) to subtract. You would end up having to figure out a way to to a cut feature. That's not what you're after.
Look closely at your geometry. Do you have a cylindrical surface mating up with a planar surface between the two bodies? When you subtract this type of geometry out, you end up with a line-to-line contact. That contact is neither solid, nor surface, and therefore SE can't figure out what to do with it but give you an error.
Also, when dealing with surfaces in SE, surfaces whos open edges are in intimate contact with a solid body, or are slightly below the body (don't extent through), often result in an error because SE doesn't know how to remove solid geometry from the surface. If you have a closed surface body, this shouldn't be an issue. This only occurs with surfaces that have open edges (non-stitched). If you have this condition, use the surfacing tools to extent the open edge of the surface past the solid body.
If your surface body has hollows in it, then you also run in to a multi-body part error because SE doesn't want to leave material floating inside of another solid during a Boolean operation. You may need to prep your surface body to get rid of any hollows or voids.
--Scott