Hmm, it really seems like a face normal problem. Instead of CTRL+N, you might have to flip face normals manually. Get into Edit mode, and then in the Editing tab of the Buttons window, select Draw Normals. You should see little blue lines protruding from each face. You might have to increase the size them more visible. After that, look at the problem faces and see if the lines point the same way as the surrounding faces. If they're opposite (pointing
into the model as opposed to out of it), select the face, and then hit either W or CTRL+F and select Flip Normals (this command is available from either menu).
Hopefully that does it.