that and why are you using union?
it's quicker than manually doing it yourself with drawing edges and deleting faces, but it doesn't always work and no one ever knows why (i doubt the programmers know why too)
btw, are the normals facing the same direction?
if you post a screen shot post one with the normals showing (Display > polygons > normal direction)