I agree with others who have said it is largely how you present the monsters to your players that determines whether your players fear a given creature or not. It doesn't really have a lot to do with stats or damage, but establishing mood, atmosphere, and a situation that works well with the creature's abilities.
That said, I'm finding that its a lot easier to make fearsome creatures and combinations of creatures with 4e than it was in previous editions. Of course, in previous editions, creatures that level-drained were always feared, but if the party knew they were going to face those sorts of things, they would stock up on Lesser Restoration or Restoration spells, and the threat was largely marginalized. In 3e and before, the most feared critters were usually shadows and wraiths due to their ability to move through walls and terrain and drain strength or levels from the frontline characters, leaving the whole party more vulnerable. For most other critters (including dragons, mind flayers, etc) there were anti-buff spells available that pretty much negated the threat of the critter, making it a sack of XP for the most part. And while straight-out damage could kill a character, I didn't ever see it happen that much- it was usually a special ability or spell-like effect that save-or-lose/rocket tagged a PC that killed them.
With 4e, each creature does less individual damage, but the critters themselves are a lot more dangerous- higher HP, better AC and defenses, good init, and nasty special abilities make almost any monster a more credible threat stat-wise. In addition, 4e pushes using a mix of critters as a core assumption for the first time, and some creatures are incredibly dangerous when used together. 4e also doesn't have the anti-buff spells to take the teeth away from monsters like 3.x and earlier editions did. These facts, combined with the teamwork aspect of play 4e encourages makes 4e fights with monsters REALLY nasty, and if a PC gets separated from the group, his life expectancy is a few minutes at best.
In the campaign I'm currently running, the PCs are terrified of ghouls, dark creepers, and zombies (normal, corruption corpses, and chillborn). The battle in question was in a graveyard, and the PCs were trying to make it to a tomb to stop a necromancer from establishing a conduit to the Shadowfell, allowing him to make a nearly endless stream of undead. The encounter was with 8 zombie rotters (minions), 2 zombies, a chillborn, a corruption corpse, a mad wraith, 2 dark creepers, and 2 ghouls (1979 XP). The group was 7th level, and had 7 PCs, so it shouldn't have been too bad according to the numbers (2100 XP being the standard). However, some bad dice luck, getting separated, the mad wraith causing confusion by making PCs attack each other, and the interaction of the monster special abilities (ghouls and chillborn immobilizing and the dark creepers sneak attack and ability to Dark Step) made this one of the roughest encounters I've ever seen in my gaming career. Add to this it was in dim lighting (night) in a very cluttered graveyard and the zombies acted as walls to hem in PCs and restrict movement, and it was a near TPK. Fleeting shapes moving through shadows, and zombies and ghouls send my group into a near-panic now, even though by the book, those critters shouldn't be bad for a 9th level group. Part of this fear is due to the way I described the situation and the mood I'd crafted, but quite a bit was due to the interaction of these critters in a fight as well.