I have this deal called "atrophied fat pads" which means I don't have the right amount of cushioning on the bottom of my feet. So they hurt alot, and barefoot kills me.
It's common among diabetics (which I'm not, just lucky I guess).
I have noticed they hurt less since going paleo, and I'm even doing some barefoot walking.
But I think a trip to a good podiatrist would make sure you get the right diagnosis. There are orthotic options out there that help a lot as well. Also shoe choices has a lot to do with it.
"I did it for money and for a woman. I didn't get the money, and I didn't get the woman"