I have an idea. A similar thing happened to me (except with the bicycle). I tried changing the header and nothing worked. I found out that you needed to press control+H and go to
Professional Header mode.
You want to pay attention to the last four numbers in the
Map Header section. If the first number is a "1" then you can ride the bicycle. I don't know if the Running Shoes uses the same check or whatnot, but it's worth a try. (Besides I noticed imported maps have bicycle problems, and even non-imported ones sometimes do, so this is good to know).
If that doesn't solve the problem, you could always put "00" at 0xBD494 in a hex editor and let you run anywhere regardless of the "map type."
__________________
"The human sacrificed himself, to save the Pokemon. I pitted them against each other, but not until they set aside their differences did I see the true power they all share deep inside. I see now that the circumstances of one's birth are irrelevant; it is what you do with the gift of life that determines who you are." -Mewtwo