well usually if you turn on triangulate first the operation will have more likely success, btw you may also change the position of the meshes: this error happen when the algorytm of TS fails creating the new edges and vertices, this happen often when some verts of one mesh are very close to verts of the other mesh, complex meshes and nonflat polys are also possible causes
with high level of identity (precision setted at 1000) TS will "weld" the close verts: less job for you, but sometimes it fails, reduce the identity factor (bring it to one), and/or move/scale one of the meshes to change the verts position.