Another overlooked element is whether or not your normals are "hard" or "soft". As a rule, any hard edge should have hard normals, and vice versa. Hence, a perfectly smooth sphere should have all its normals set to soft. Consequently, a hard edge (as where two planes meet at an angle) should have hard normals along the edge in question.
This often becomes a problem when appending to the polygon (ie replacing/repairing deleted faces, &c), as the new normals aren't necessarily as hard or soft as the ones already on the object.
To change the hardness/softness of normals, select the offending edges (or faces) while in component mode and go to Edit Polygons>Normals>Soften/Harden and choose the selection box. When in the selection box, you can select any value between 0 and 180 (zero being all hard, 180 being all soft) to adjust the hardness/softness. Play around with it. I have found it indispensible in making hard surface or organic models look just right!
Hope this helps...