My process is similar to what @Seraphim73 mentioned. I start with an "elevator pitch" - or what Fate would call "high concept". This usually has three parts: a professional hook, a theme hook and a complication.
For 100 MUSH: "veteran archer (prof) who served in the Ice War (theme) who's all 'I'm too old for this s----' while saddling up for yet another conflict (complication).
For BSGU: "mob doctor (prof) for the Space IRA (theme) forced to work with the enemy for the greater good of defeating the Cylons (complication).
From there it's just a matter of fleshing out a few key details to make the character three-dimensional - family, career path, hobbies, that sort of thing. I use my character creation article as a guide but rarely hit every point for every character. Unless some important bit of personality falls out of their background, I usually don't figure that out until I start playing them.
I'm somewhat leery of pre-existing background ties with other characters. It deprives you of a lot of the MU bread and butter "getting to know you" RP, and it strains my inner sense of continuity because there's so much about the relationship that my character would know that I don't. I'm not the best at winging it and often feel off-balance playing that sort of thing. But I have done it sometimes - siblings, cousins, old comrades, old flames - and it can certainly be interesting.
I will totally replay concepts, though the theme hook and complications usually help me put a fresh spin on it each time.