It's funny, but people think 4e is "only a tactical mini-game" but the inclusion of the half-level feature in 4e meant for me that I would use more skills and I would use things like History and not be worried that a character would feel left out.
Actually, this is part of the problem, not part of the solution.
Keep in mind that I really like the idea of giving everyone some basic-level competency at doing tasks. This can even increase with level, and I'm not too worried (3e wizard has a bigger BAB at 20 than at 1, even though he never whacks things with his staff or shoots his crossbow).
But the fact that everyone has approximately the same skill bonuses at every level means that you aren't left out, but also that nobody is anything special at doing anything. There's no meaningful difference. I could train in History, or not, and it wouldn't matter, because the guy who chose to train in, say, Perception, will get the same bonus to his skill challenge check as I do, assuming he bats his eyelashes right at the DM.
Now, this is something that 4e is changing. Skill powers, more rituals, tinkering with exclusivity, these are all great things that make having a different skill actually matter.
Of course, it still doesn't matter in a
skill challenge, but that's honestly more the fault of the Skill Challenge system than anything else.