That's because of the limitation of approach of how inner/outer surface are calculated in Boolean modifier. Current Boolean uses Carve library. Carve will perform boolean operation only if the intersection of two meshes is a closed loop of edges.
As shown in your image, the object is not a closed manifold one, which confuses the edge classifier. This is listed in Boolean modifier limitation.
To solve this, I suggest adding a Solidify modifier on top of Boolean modifier, with a very small Thickness Value (such as 0.00001
). After applying both modifiers, you can press W > Remove Doubles to clean the mesh, and select all faces, then press Ctrl N to correct normals. (This sounds like a trick, but it works in this case, since there's nothing you can do with the current Boolean approach, which got its own advantages as well as limitations)

Example file
By the way, in the coming 2.70, Boolean modifier supports ngons, which means you can generate much better and cleaner results (as shown in above image). You may want to give it a try.