A friend of mine who also DMs had similar issues; he found that players fell back upon "well, let's break it/kill it" as a strategy too often because of how good their characters were compared to the world around them. He once commented to me that he no longer saw the point in trying to run social encounters because too many of his players would attempt to just kill the other side if negotiations didn't go their way.
It's weird, my experience of 4e is the exact opposite. I was used to 1e with its F0 men-at-arms, and 3e with its default Warrior-1 men-at-arms (according to Monte in the DMG); basically a world where non-BBEG NPCs were by default utterly helpless vs high level PCs. 4e doesn't work like that at all; my 10th level 4e PCs see a dozen tough-looking guys ahead and they are still nervous, just as they were at 1st level. I find social interactions in 4e are far more reminiscent of the real-world than in any previous edition. Recently my group overthrew a small monarchy at 8th level; the Bandit King Boris of Llorkh who had a couple hundred men. In 1e an 8th level PC group could easily have wiped out Boris and all his men. In 4e it meant political shenanigans by Esmerelda the PC bard (believed by many Banites to be the long-prophesied Bane Child), getting the Banite faction within the bandits on-side, whipping up outrage over the death of Boris' mage-seer Olaris Vlakos due to Boris ignoring Olaris' prophecy re time-travelling ogres in the catacombs... a final confrontation in the throne room where the PCs had the numerical advantage, and a dramatic duel between Boris (Brawler Fighter elite Soldier 9) and his PC-supporting Banite fanatic daughter Kitana (elite duellist Soldier 8). Boris KO'd her, but was eventually himself KO'd by the PCS & weight of numbers.