Ugh. It appears to work very randomly. Any other tricks?
No; but one thing you need to make sure of: The order.
Spawn the cube FIRST
Select your model
THEN select the cube and hit ctrl+j
Go into edit mode and delete the cube
When you select the cube first, it doesnt work.