I will not diagnose, but it certainly sounds like plantar fascitis, or inflammation of the plantaris. This is likely due to over use. You can also try a tennis ball in the same fashion as the water bottle, and try pulling a towel with your toes until it's past the toes.
To heal microtrauma from over-use, you have to let the plantaris rest. Because you have a high arch, I believe seeing a podiatrist (and conversely a pedorthist) will be in your best interest.
Store bought solutions are typically not a great solution, unless your feet are in perfect biomechanical condition (most people aren't). Be sure to seek proper custom (made for you, and you alone) orthotics, and from a pedorthist who makes insoles in house-be wary, as many pedorthists send their stuff out. Custom orthotics aren't typically cheap, but your feet will thank you. Your podiatrist should have pedorthists to recommend, but once again, be wary-I've heard horror stories.
Proper footwear should feel better right away-you typically shouldn't have to adjust to it unless there is something else going on, like you're trying out Fivefingers (safe to say those are contraindicated for you; more for those who have perfect feet again)
Full disclosure, my father is a pedorthist. He makes his stuff in house. That is not where I'm getting the majority of my data though-I am a professional in exercise science.