It sounds like the normals to me,

go back in the history to before you combined the poly objects, select one of the parts and reverse the normals (in maya 8 Normals have a menu of their own, in previous versions they are under the edit poly menu). Now when you combine the parts and merge the verts you shouldn't have any problems.

Take it easy,

Mat.