I used to have the strangest walk imaginable, and it got weirder in high school. Used to bend my knees and kind of bob/gallop along, and though I KNEW I had a strange walk thanks to comments and teasing from others, I couldn't correct it. I only became more self-conscious about it, which made my gallop even more pronounced. One of my classmates had the gall to ask me why I walked that way, and I told her that I'd been in an accident that hurt my knees.
It wasn't until my early twenties, after much practice (keep head up, back straight, knees relaxed) that I began to walk somewhat normally without too much trouble. I still need to carry a comfort item, however, to truly feel at ease, like a purse or coat. 