The block disappears on one side of the plane but the other side becomes part of the plane. Anyone know what's going on?
Thee problem is most likey due to your meshes not being manifold (ie, completely enclosing a single solid volume). The plane is obviously non-manifold (being just a plane) and the blocks are technically non-manifold since they enclose multiple volumes rather than a single connected volume.
The Boolean modifier includes a 'Solver' setting. This allows you to choose between BMesh and Carve and these use different methods to apply the boolean which can produce different results - especially with non-manifold meshes.
I can replicate your results using Carve and switching to BMesh produces the expected cut-out.
NOTE : The Solver option was introduced after Blender version 2.76b. If you do not have that option then you'll need to address this in a different way - by making the meshes manifold as this results in the modifier producing more consistent results. To make the plane manifold you can simply add a Solidify modifier before the Boolean modifier. With the plane manifold both solvers should produce the desired result.