People usually blame a mineral deficiency for muscle cramps. It could be potassium, magnesium, even sodium. Magnesium's probably the one to start with.

I bought some running shoes and ran in them a few times. Eventually I started getting horrible knee pain whenever I wore them. Running barefoot, or in Vibram FiveFingers, or even in Tevas, doesn't seem to hurt my knee at all, though.