It's red because there's no object selected to Boolean with. When I picked the other Cube it worked fine. You might need to update your Blender to 2.74
The "Cannot Execute Boolean" is because of this beauty:
In this case the geometry was obviously a bit untidy. But it can happen that this similar situation happens at much smaller scales, which are less easy to see without zooming in. In this case the manifold check in the 3d printing tools doesn't pick it up either.