Make sure you don't have any problematic geometry, like duplicate faces on top of each other. An easy way to test that is to select an individual vertex and move it around, to see if the connecting edges behave properly. Or just delete a single face. If that is not the case (I suspect not), then try selecting the problem edges and use Normals > Soften.