We use both.
My group started using backgrounds when they came out, and at the time, they seemed like a relatvely minor addition. Again, at the time, they were. Just some basic skill-benefits; a plus two or having a skill on your class list that otherwise wouldn't be is not a big deal. This was, of course, before the Forgotten Realms backgrounds came on the scene.
My group started using themes when I launched my most recent campaign (nearly a year ago now). We chose not to introduce these new elements in the middle of the previously running game, as it would have been a lot to absorb all at once (we were 9th or 10th level by that point).
Being as it's much easier to introduce new things like this after a hiatus, we will probably end up retroactively applying themes to all our campaigns eventually. Themes feel, to me, like the missing element of character creation. They fill the niche that Kits took up in 2e - interesting ways to differentiate your character mechanically and, ahem, thematically.
The power creep is another story though. As others have pointed out, themes are very hit-and-miss as far as mechanics go, and some have abilities that can really break the game in the wrong hands. Optimizers simply use them as another element to min/max. I'm not even worried about the extra power at first level - most of those aren't too bad - it's the skill bonuses that tempt me to ban things.
There are too many overly generous bonuses to skills, most of which could be solved by making them not stack with anything. In the case of both background- and theme-based skill bonuses, most of the issue can easily be eliminated by making them feat bonuses. The problem arises when you take a background that grants a nice juicy +3 to a skill that lines up with your prime stat (some of them even give training too!) then combine it with a theme that gives a +4. Stack an item bonus and a feat bonus and you're into the low +20 range by Paragon. That's insane. I had a fellow player that cranked his skill up so high with this that he could routinely make checks (and I mean routinely) that were 10 levels higher on the revised DC chart. Ten levels. A FULL TIER. That's ridiculous.
Bonus points if that skill is, say, Arcana (it was), and you then take a bunch of Cantrips, Skill Powers, and Utilities that allow you to substitute it in place of other skills (and there are a lot of those), and congratulations, you've just made every other character (even the focused skill-monkeys) irrelevant at their best skills. That's shades of 3rd edition right there. Extra credit for taking something that allows you to reroll Arcana if you fail or don't like the result.
Now, granted, most of those are encounter powers, but you often only need to roll once on a given skill in a given encounter. When you have abilities, all of them separate encounter powers, that allow you to substitute one skill for another, suddenly, you are a one-PC skill challenge crushing machine.
It's like the skill challenge equivalent to Expertise - while the bonuses are nice in that they theoretically allow you to branch out in ways that would be subpar for your character otherwise, and give you the bonuses to make it worthwhile - in reality, they serve only to widen the gap between optimizers and everyone else. I like having an effective character as much as the next player, and have nothing against optimizing in general, but this is an issue with themes and backgrounds that really needs to be fixed.
