Wonderful.
Here is what I learned about smoothing...the trick is to pick groups of polys to smooth at a time, and try to be patient. If you smooth and come up with errors, it means the smoothing group is trying to smooth polys that are either not aligned in a reasonable plane, meaning that if you looked at the poly from the side one or two of the vertices would stick out compared to the others, or that the angle of one group of polys compared to the other group inside the ones you selected to smooth is too sharp.
In the case of the out of line vertice, I try to bring them in line...I look at the group from the side (the poly disappears) and look for those dots sticking out, moving them slightly until the entire poly set disappears. You can usually see where vertices are out of line if you look at the mesh group with no smoothing in place.
In the case of the angle that is too sharp, I will either reduce the angle of the sharpness (by lowering one set of polys so the angle is much less steep compared to the other set) or I will just choose, or break up the set that is closer matched and smooth them seperately, like you did above.
Finally, you can reduce the smoothing effect, one point at a time, until the edge you are trying to bring out pops into view. That will works sometimes as well.
This usually solves overall smoothing issues. Sometimes it also helps to increase the polys in an area to make it smooth better but cutting them in.