Seriously? It depends.

You might, for example, have an object that is non-manifold or is otherwise not valid for the operation. But if you're trying a sphere/cylinder or cube/cylinder combination, those ones are just wierd (this is one of the situations where maya kills the shape on mine, don't know about yours). As near as I can tell, the best way to solve that particular problem is to select a cylinder (or a resultant from a cylinder) and then the other shape.
If you're trying to work with non-manifold geometry (the 'polygons>cleanup' operation will take care of most of these (i think)), you may be stuck.

So how about more specifics?