Are you selecting both objects, and then just clicking 'Merge Vertices'? The settings may be off, causing the verts to have to merge with the wrong vert on the other object.

Also, did you make sure the normals on both objects were facing in the same direction?

If so, and it still doesn't work, pbman's suggestion should work just fine.