Check the normals on both sides of the border edge and make sure they're facing the same way. This can also be caused if you have messed up geometry there - try to select one face and make sure there aren't actually two faces there (in the same place).
You might need to use cleanup but it usually doesn't get that far if you have good working habits.
Benny