Wow, I had no idea trying to explain your abilities was so difficult. Heck, I have a 17th level character, with 4 classes, a multitude of special abilities from those classes as well as feats, and 25+ skills with ranks in them. I am certainly not an optimized character, but I can explain almost every single choice and can provide short stories for many of them. For me, that is a lot of the fun of the character. I like providing backstory. I can also provide backstory for a focused fighter, after all, he is picking up feats. Maybe he has a few mentor's in the Royal Guard? Or a rogue, perhaps honing his skills at the guild, or if he isn't a guild thief, perhaps he buys a variety of damaged locks, pulls them apart and puts them back together again, learning more about locking mechanisms. (To steal a concept from Gary Gygax). It is all backstory that allows the player to create interesting little stories.
I am going to go out on a limb here. Based on John's past posts, I don't think he is looking to be too much of a hardhead on this. He is just looking for his players to put a little more thought into the character and assisting in the storytelling of the game.
As a DM, I like those little details as it helps me add hooks for characters as well as flesh out the campaign world so it seems more dynamic and alive. As a player, I try to give my DM those little hooks. It creates more dynamic storytelling and is something that I think should be encouraged.
John, I would suggest gentle persuassion. Not all of your players are going to be eager to deal with boring backstory. The key is that backstory doesn't need to be boring. Be generous with the RP benefits tied to backstory. As an example, if your fighter spends a lot of time with the local guard/militia, let him be friends with the commander. Through story leads to the character through his friend. If they get into a brawl and the militia shows up, let the character off with a friendly rebuke from his friend, that captain. Little things like that will help.
You can also use some of the more tangible benefits that BiggusGeekus mentioned. Just don't hand out anything that is useful in the standard adventuring gear type of useful. If you do that, than the players that are a bit more reluctant to extend their reolplaying will have legitimate reasons to gripe. You want to gently encourage them, don't use a big hammer.
For my latest campaign, I asked for character concepts before the game started. Part of this is to encourage strong roleplay. But, the bigger part is that I have added a bunch of house-rules and I want to be able to point out options that are not in the Core books. I didn't want to heavy-handedly make my players roleplay, I wanted to be sure they didn't limit themselves just because they weren't aware of all the options. (I would like them to be familiar with all the books I am including, and all the rules, but that isn't a realistic expectation.) My point is that it is important to explain some of the reasons why you want information from your players. If you want a little richer storytelling experience, tell them that. If you want backgrounds and class rationalizations to help give your story elements, let the players know. With a lack of information, it is easy to assume that you are just being a jerk.
Hope that helps somewhat.