This book definitely produced PCs with personality:
The randomness inherent in its system is probably a poor fit for 4e, but it could serve as a good source of inspiration, if you can track down a copy.
On a more serious note, I'd suggest asking the players to answer a handful of fairly broad questions. No need to get into too much depth before the character ever sees play, but enough for the player to get somewhere to start.
The backgrounds in PH2 are a good place to start with developing a bit of a personality/backstory, and I think they are great for overcoming the "writer's block" that many players get when starting with a completely blank slate. Pick 2 to 4 that seem applicable, and maybe even let them get mechanical benefits from 2 (instead of just 1) to encourage picking more than one background.
Many of the backgrounds will provide a starting point for answering questions like: Where did you grow up?
Establish some motivations for the character, including at least one short-term goal and one longer-term goal. Neither goal should be something very time-sensitive; "to rescue my sister who was captured by slavers" is good if the first adventure involves a group of slavers who just so happened to capture the character's sister. Beyond that, it's hard to justify going on other adventures while someone's life is in danger. Of course, that could establish something about the character's personality...
Ask each player to identify one significant person in their character's life; it could be a mentor, a parent, a sibling, a friend, whatever. What was the character's relationship with that individual? Is he or she still in the character's life? What influence did that person have on the character?
Something else that might be helpful for getting the players thinking about it would be to ask more targeted questions, such as "how do you react when you see someone being bullied" or "how do you respond when threatened?" "Entrusted to deliver an uncounted purse of gold, thou dost meet a beggar. Dost thou deliver the gold knowing the trust in thee was well-placed; or show compassion, giving the beggar a coin, knowing it won't be missed?"
The short version: ask the players directed questions or give them lists to pick something from to get them started. Sometimes narrowing the options can really get the gears turning.