Normals are not really related to UV's.

Send me your file and tonight when I get off work I'll take a look at it.

I have a feeling that even if your face normals are all nice, your topology isn't doing the trick (5+ sided polygons can cause some problems with shading). - I was wanting to do a video on this. Can I use your file as an example and show how to clean it up?