I'm in the same boat myself. I don't have an authoritative answer to it, but I think it really just boils down to any given form of exercise targets a different form of muscular and cardiovascular exertion and performing a particular set of motions has an aggregate positive effect, but doesn't necessarily apply to the next set of motions. Walking is a different form of exercise than running with a different motion and impact.
As for me, the primary thing that I've found works for me is slowly transitioning into the exercise. It feels really awkward at first, but start with jogging slowly, and not for very long. I know that, for me, I assumed running was more or less a slower sprint, but there's a difference in gait. Starting slow lets you more gradually accustom your body to this different form of movement. Additionally, starting slow decreases the impact. I walk very fluidly, but I'm still working on running and not feeling like I'm jolting myself at every step. Pay attention to how your gait feels. If it feels like you're literally pounding the pavement, you're probably not doing it right. Pull back a bit more on the speed and consider how you can land and push off on your feet to make maximum use of the elastic properties of your foot structure.
I won't lie... running is not easy to get into for some of us. But I can assure you that, if you take things only as fast as you're comfortable, it is possible to transition into.
Lastly, general caveat, if you're instantly out of breath, especially if your chest and throat get really tight, get yourself checked for asthma. Walking might not be triggering it because you've naturally adjusted to never push yourself past that threshold of effort, but the unfamiliar action of running, the stress of it, can serve as a trigger for a breathing problem you never knew you had.