After you do “Remove Doubles,” and if it doesn’t completely solve the problem, look over your geometry very carefully. You might find things like “interior faces” (my term), which are “inside” the object but don’t need to be there, and you might find “intersecting” faces where one face protrudes through another but there’s no connection between them. This is the sort of thing that can confuse the renderer.
Also, after doing all the cleanup you can, “recalculate normals outside.” The normal-vector, as you probably know, is an imaginary vector that points “out of the front side” of the face. You know where “the front side” is supposed to be, but Blender’s just a piece of computer software. This step will recalculate the orientation of all of the surface normals, so that they do point “outside.”
Finally… I routinely go into Edit mode and “select all.”