Try Edit Polygons > Normals > Set Vertex Normals. When you soften your edges, you'll probably need to adjust your threshold angle to prevent it from happening again.