The problem is that the boolean operation is sometimes very tricky. There are much things to attend. Search for a Thread at SM there I asked the same!
I didn´t made the cartoon Dog Tut. but I think that you have to combine and than to merge the verts!
That means you have to delete the unnecessary faces, combine the two Meshes and finaly Merge The verts!