Booleans can be very tricky sometimes. You may experience problems when your geometry is too complex, when you have too many objects intersecting in a small place, or when the history on your objects is lengthy.

First, try choosing Edit>Delete by Type>History and try again. If you still have no luck, post an image so we can see exactly what the setup is. If we can't figure it out then, you may end up having to attach the actual scene file so we can look at it first-hand.