Have you been fitted at a running store for proper shoes, based on your arch, etc.?
How old are your shoes?
Have you considered going to a podiatrist?
Does it happen at certain times of the day (i.e., first step of the day vs. during exercise)?
I have had plantar fasciitis, but that's different from the type of pain you described. Honestly, I'd see a podiatrist if I were you.