My wife has similar-sounding pain. She was diagnosed with Fibromyalgia (which, as far as I can tell so far, appears to be in many cases a diagnosis of exclusion - we don't know what causes this, so we'll put it in the Fibromyalgia bucket) and Ehlers-Danlos Syndrome, which makes her connective tissues weaker than normal.

We have tried quite a few things with varying degrees of success.

• Trigger Point Therapy - A type of massage therapy that focuses on treating a muscular phenomenon named (poorly, in my opinion) "trigger points". In brief, these are small regions of muscle that become constantly contracted and unable to relax. I'm not aware of the specific mechanism that causes this. Trigger points can have strange effects, including pain appearing in different parts of the body than where the muscular problem exists. The best resource we have found on this is this work by Travell and Simons. Here is the volume for the lower extremeties. We have had good success with this sort of treatment, but we have to keep treating. It's worth investigating, even if the problems seem like joint or nerve pain. Many of the referred pain patterns appear in joints, for example. I don't know how well-researched this phenomenon is - many doctors seem to be unaware of it's existence.
• Other forms of massage therapy give her some temporary relief.
• Aquatic physical therapy - This involved exercises and stretching in a pool kept at about 80F, and it seemed to have a large positive effect. I'm not certain of the exact exercises done, but if you're interested I can find out.
• We have explored possible dietary factors, and have found that removing wheat has some effects on other conditions, but we can't correlate it strongly to pain.
• Stress reduction - Stressful events cause her pain levels to rise quite a lot, and it takes quite some effort to bring the pain back down after an event. It appears that the pain and stress work in a positive-feedback loop to make things worse.
• Alcohol - We've discovered that she hurts much less when mildly inebriated. Obviously this isn't a good solution, but it does offer some temporary escape from the pain.