Ok another possible cause is that the normals are not facing the same on both pieces of geometry, not sure what version of MAYA you are using but you should be able to check the normals of an object by selecting it and under the Display tab by going to polygon components and selecting face normals.If you find that the normals are not facing out one piece then revoerse the normals on that piece and try the union again.
Also deleting the history is a good idea befor performing a boolean.