Backwards normal issues
If recalculating the normals via ctrl-n or shift-ctrl-n, on individual linked pieces, doesn't work correctly, you have bigger problems than discontiguous normals.  You probably have geometry that is non-manifold in other ways-- zero length edges, doubles, edges joining more than 2 faces, etc.  Use ctrl-shift-alt-m in edit/vertex mode, disable non-contiguous on the operator panel, and start cleaning up your mesh.