Boolean Union vs Difference Error - Swapped Behaviour
I had this exact problem about a week ago.  IRC told me that the face normals on one of my objects were probably backwards.  It turns out they were correct.  

You can turn on the display of face normals in EDIT mode using one of the icons in the Mesh Display section of the N pop-out panel.  

You can reverse the direction of the normals of the currently selected faces using the Mesh > Normals > Flip Normals operator.  There are also some "smarter" operations in that same menu.