Boolean modifiers on an imported object

I’m having some issues getting boolean modifiers to work on a set of objects.

Firstly, here’s my blend file: http://www.pasteall.org/blend/30552
I imported a map object from a game and placed spheres in locations around the map. What I’m trying to do is get an object representing the parts of the map that are not contained in any of the spheres.

I figured a boolean difference between the map object and the sphere objects would be exactly what I wanted, but the result of the difference was this
http://i.imgur.com/EaK5Jvd.png
and the result of a union was this
http://i.imgur.com/OVD1vZd.png

I then added a second boolean modifier for another sphere, but the second modifier gave a “Cannot execute boolean operation” error.

So, I tried joining all the spheres together and using a single boolean difference, but I got the same error. I then tried a boolean difference between the spheres and a large cube with the goal of intersecting the result with the map object. I was able to subtract the spheres from the cube, but got the same error when trying to intersect the cube and the map object.

Here’s the cube with the spheres subtracted, and the visible parts of the map geometry are what I want to “get rid of”:
http://i.imgur.com/kovdXnH.png

Is there some crucial step I’m missing in order to accomplish this, or is there another way to approach this?

Thanks!

Recalculate the normals on all objects that will be booleaned.

After recalculating normals on all the objects, I’m still getting “Cannot execute boolean operation” when applying modifiers to (or targeting) either of the map objects (hangemhigh in the blend file).

Okay, I looked at your .blend, you have non-manifold objects. Boolean to work correctly must be on manifold objects.

Edit: Correction, it can work on non-manifold objects, but if the boolean is on the edge where the object opens, it will fail.