that is usually cause because the verts are not merged together, when you used cleanup it might have seperated them because the surface normals were not comforming ect.
