I have coldness and pins and needles. My hands and feet can get so cold it really hurts. I keep a heating pad in my office to warm up my feet when I'm working and last winter wore cashmere socks. This year I'll try the stuff hunters put in their boots and see if that helps. when I get them really warm with the hot pad it seems to break the cycle and they'll stay warm as long as the room isn't cold.
Small fiber is my diagnosis so far.
There is a auto immune disease that makes you cold but them your skin looks blue. If you have that symptom see a rheumotologist.

I also have a similar problem...my toes get very cold and hurt. I have a warming pad (actually looks like a door mat) that I use under my desk to keep my toes warm at work. It was a bit pricey but it was worth it. I keep it on all day and keep my feet on it, works wonders....