On this image I selected four vertices and then I pressed F to create a face and I repeated until I connected the two parts of the object. Then I deleted the "internal faces". But the shading is still wrong. Recalculating the normal doesn't fix it. I deleted one of the faces and recreated it and the shading on it was correct. What is causing this un-smooth shading and how can I correct it?
When you add faces using F to a mesh they default to Flat shading - even if the rest of the object is set to Smooth shading. To set all faces to Smooth shading in Object mode, simply click 'Smooth' shading in the toolshelf (T). Alternatively, in Edit mode, simply select those faces, press Control-F to bring up the Faces menu and select 'Shade Smooth' (or 'Shade Flat' to set individual faces back to Flat shading).