I agree. The increased number of viable options for every character, as well as the increased number of actions per turn, make 4e characters slightly more difficult to run than a comparable 3e character, excepting 3e spellcasters.
How this plays out in my game (and I'm a player!) is the kind of indecision paralysis that can result when there are many options and few clearly superior or inferior choices.
Making some of the amendments that people have suggested helps. So too does limiting people's time per turn; some people like to ponder, when really it is almost always more fun to move combat along as quickly as possible. Limiting time to, say, a minute per turn really hasn't hurt anyone in our group in terms of decision making; we are not making bad decisions or forgetting details when before we made good decisions because we had all the time in the world.
I find terrain really complicates this. If there are a number of choices to be made about terrain, there is a cost in complexity and choice.
Given all this, however, I think the extra complexity is worth it. The consequence of 4e's options is that players may have to learn the game better and make quick decisions. There are no really simple character options in the game.
That is preferable, though, to characters that are simple to play but cannot play at the same levels as other character types, as is the case in 3e. Of all the simple character types in 3e, only a small handful are even effective at doing what they do in a 3e game beyond low levels. It might be nice to have a 4e character that is simple to play, but even the effective simple 3e characters were such that players generally had a particular action set in mind to be most effective; the same is possible for a 4e character, so you can plan in advance.