The problem you're having has nothing to do with the number of faces on the shape but, rather, the direction of the normals on the contained vertices. It looks like each vertex has a set of normals for each face instead of sharing one normal between connected face. You can see what I mean by turning on Vertex Normals (Custom Polygon Display options box). For the vertices connected to the faceted faces, you should see a bunch normals emanating from them. Anytime a vertex has more than one normal, you will see a sharp edge in the shading.

There is a simple solution for your problem:

Select the faces you want to smooth out.
Go to Edit Polygons -> Normals -> Average Normals.

You can probably get rid of those extra faces from the smoothing/subdividing. They are completely extraneous.