And since I am now certainly in this conversation, might as well add my part to the mix:
We agree on this one. If you play combat through like a monster mash, then yes, it can take a while. If you mix it up with narrative though, you can diversify what is going on and even though it might take a while, it won't seem like your constantly fighting. There were a few things I did to help with this in my game.
I reduced the monster HP by about 20% so they didn't take as long to defeat (kill, gave up, etc), In some cases I dropped the AC by 1 (depending on what role the monster had in combat), and I adjusted the monster damage so it had a bit more pop to it. The reason for the adjustment, and perhaps I was not the only one who noticed this, was that when I first started off my players, they felt the combat was really hard. I believe my wife at one point said "When did goblins get tough?" when she was either 1st or 2nd level. But then around level 5-6, the combat got easier, almost to the point of boredom. Then when they got to level 11, it got hard again. And then again, around levels 15-16, it started to get easy again. To offset the wave, I didn't do anything with the math, but I did up the damage die with the monsters by 1 around level 6 and then again around level 15-16. I figured, if the trend continues, that I will have to do the same thing around level 25 or so.
Another thing I did was that I started to make combat-based skill challenges, similar to what you stated above. This is a skill challenge intermixed with a combat situation. One of the last one's I did was that I had a white dragon attack the parties air ship and the monster attacks were based on what was in the stat block, but the effects of the attacks on the ship and what the players might run into with the dragon during the attack was part of the skill challenge. They had a lot of fun with it and came up with some really creative ways to use the ship to fight the dragon.

Combat still lasted a while, but there was so much going on and they were having so much fun, the players didn't notice or care.
IMO, this complaint is the biggest load of bull I have ever heard from the gaming community about 4E. You don't need a game system to effectively role-play. If you feel you cannot role-play with a given system, then your not trying to role-play. Your just trying to play a game. If that is your speed, that is fine, but be honest about it and don't make up stuff to compensate for your vanity (grumble, mini-vent). With that being said, it is also important for the DM to have a solid grasp on the mechanics so they can tell the story in a meaningful way that the players can feel engaged in. 4E is a VERY modular system. You don't even have to run combat with the combat rules if you want (hello skill challenges!). You can have high magic, low magic games, you can have games with no magic (look at DMG2 if you are not sure what I am talking about). The idea that you cannot role-play with it is just nonsense................
It took me a while to understand what was going on with Skill Challenges. Videos online from PHD20 and the blog At-Will (not sure if it is still up or not) helped a lot with this. Also, the article on Narrative Challenges in Dragon Magazine which was developed for downtime activities in 4E added a new element to Skill Challenges that I had not seen in the core books. The biggest thing for me was "What story am I trying to tell with the challenge?", "What actions are the players going to try to do in this situation to resolve it?", and "How do the skills play into the player's actions?". I found the easiest challenges for me to write in the beginning were group challenges that progresses from one stage to the next that the players were reacting to. I play-tested those for a while and then evolved what I had to include other situations. I would also playtest skill challenges and rewrite them based on how the players interacted with them until they did what I wanted them to do. Right now, my skill challenges are subdivided into combat challenges, social challenges, environmental challenges, reactive challenges, and hybrid challenges (where I intermix elements of the previous ones together for the challenge).
The best thing for this is to remember that the rules are there to facilitate plot points for story telling. As long as you keep that at the central focus, you should be fine.