I don't think it would be the nornmals. When the normals are fliped from each other and you merge the edge it just twists one of the faces.. at least thats how it aways dose for me.. (grrr)
Try merging the vertices like mike says though. if that dosn't work thin see if you have anything wierd like duble edge or something.