The problem is that your faces are triangles. Triangles are notoriously difficult to smooth-shade.
The short answer is that you need to convert your triangles to rectangles (quads).
To do that, you can take advantage of a built-in Blender tool: "Tris to Quads." Select all the faces that you're having trouble with. Then press space and type "tris to quads" and then select the matching command. This will automatically combine triangles into quads, where possible.
But this might not quite work the way you want it to. If it makes awkward quads, you might have to undo that and try something slightly different. Try changing to "face select mode" and then select two triangles that would make a tidy quad. Then press space to run the command again. You might have to this for each pair of triangles, but it'll make the shading much more smooth.
So, avoid triangles where you can. Use quads as often as possible.