Things to be sure to check are:

1) intermittent claudication-- this is where the circulation to the feet and legs become impaired. It is more common in smokers, males who smoke, or the elderly.

2) check for foot issues... the sesamoid bones can generate alot of pain if broken or dislodged. The increased concrete walking pain, suggests this to me.
This usually does not make the legs hurt, unless you are walking in a way to strain the hips.

Sometimes it is really elusive to find the causes of pain. Most of us can understand your frustration very well.