AbdulAlhazred
Legend
See, this is a bad idea, I think.
Most people have a reasonable idea of what they're building by the time they pick a background. They'll have chosen a race and a class, possibly chosen a name and even mostly settled on what the character can do - the weapons he wields, etc. When you're chosing a background people may already have a rough idea of what they want. If all the backgrounds merely grant a class skill or a +2 bonus, then this step devolves into "hey, this character wants bluff - but he's a wizard, hmm, let's see" and picking whatever possibly inappropriate background.
The backgrounds as the PHB2 presents them don't inspire any ideas, they're just a way to distribute skills a little more flexibly. Their monotony rejects the notion of actually browsing through these things for anything but mechanical benefit. And, suddenly, if you think you've found a background that seems fitting roleplaying wise but whose associated skills just don't mesh, you're kinda pushed into "selecting" another background. And it's quite clear many of these backgrounds are quite amusing, but the one or two associated skills only vaguely cover the flavor.
I think the associated language benefit works for regional backgrounds. Predefined associated skills are almost certainly nonsense. Fortunately it's usually not a big issue since your class probably covers most of them - but that doesn't mean I like the mechanic at all.
Backgrounds should either be at least interesting enough to browse - or they shouldn't limit selection of associated skills. Don't impose non-sensical roleplaying backgrounds on skill choices, which is what PHB2 backgrounds effectively do: instead, let people pick a background and choose an associated skill themselves - or make sure the backgrounds' benefits are varied enough to be interesting.
I think you're mischaracterizing backgrounds. Lets look at the mechanics of it. A PC gets to choose at least the following elements: Geography, Society, Birth, Occupation, and Racial (some books may have other elements and each campaign will likely also have Regional). That is either 5 or 6 elements of which they can choose one or more. Every one of these has at least one associated skill and possibly a language. The player thus has 5-6 skills to choose from for his character. If he doesn't find something appropriate he can simply make something up that works for him. That means no 'shopping' necessary. The skills just give little hints to say this or that might be cool and appropriate for his character concept. Once you've worked through that list you WILL have whatever you wanted. Its not going to work out that the player picks something FOR the skill. He picks something interesting, it gives him a skill he can use and probably the one he would most like to focus on for that matter.
Personally I've found that it works out quite well. I've gotten FAR more detailed and interesting backgrounds from the players using this than I had in the past. Honestly most of the people I play with would do some level of background anyway, but the PHB2 system does kick them in the brain cells some and give them stuff to think about. I tell them to write a paragraph about their character and point them at PHB2 and they generally don't even write down the 'choices' they made, they just say what the character did before, etc and that they get +2 on whatever skill for whatever reason. I don't question this or try to get them to nail down that it is from "Geography" or "Region". I don't really care. It just works.