I noticed drier skin after about a year of paleo too.
I did a bit of research, and learned some interesting information about iodine. Apparently, one potential downside of cleaning up your diet and ditching processed foods, is that you get a lot less iodine in your diet. The theory is that by eliminating processed food high in sodium (and iodized salt, since 70% of industrial salt is iodized) your body's iodine - the substrate for thyroid hormone - is depleted over time. Lower thyroid function (due to inadequate iodine) can cause dry skin, cold extremities, low energy, and a whole host of other symptoms (Google hypothyroid symptoms).
I've never restricted salt usage, but in addition to giving up packaged, processed foods, I switched from regular processed iodized table salt to a minimally processed sea salt awhile back. Obviously, it would not be artificially iodized. Another factor, is the increased consumption of goitrogenic foods (which block iodine uptake) like cabbage, Brussels sprouts, kale, broccoli and cauliflower - even strawberries and peanuts contain goitrogens. Speaking for myself, I KNOW I eat a ton more of those foods than I used to - especially cabbage and cauliflower. Chlorinated, fluoridated tap water doesn't help either - both chemicals block iodine uptake.
Dr. Weston Price wrote in his book that the people who lived in the mountains (I think it was the Peruvian Indians) would go to great lengths to trade for dried fish eggs. When he asked them why they consumed the dried fish eggs, they said they didn’t want to get “big necks like the Americans” (goiter). So... if you're not eating fish and seaweed everyday, you might want to consider iodine supplementation. About a month ago, I started taking several drops of Lugol's 5% Iodine Solution in my coffee each morning. My skin is noticeably softer, I don't get chapped lips anymore, and my hands and feet seem warmer.
Dr. Davis talks about this stuff in his blog too:
http://heartscanblog.blogspot.com/2009/08/iodine-deficiency-is-real.html
Richard Nikoley blogged about iodine as the "Hidden Benefit of the SAD" here - http://freetheanimal.com/2010/01/the-hidden-benefit-of-the-sad-iodine.html