I'll throw my 10 cents in -
My first impressions of the HE-400 are that they are quite "lean" sounding, but spacious and very accurate. I too expected a "recessed" mid-range, and was concerned that they might be too laid back to really like. Right off the bat I noticed a lot of texture, especially in bass lines. They were not "bright", either, but I certainly wouldn't call them warm. My HD595s were considered "bright" for Sennheiser, but what that amounted to was a slight bit more treble emphasis.
I listened to them for days and this impression started to fade - they became more "aggressive" sounding to me, with a "subwoofer playing that I can't turn up".
Then I got my little O2 amp to see what more power might do. I now think I was on crack.
If there is a "recessed midrange" I don't hear it - these babies translate lyrics for me I could never make out before. They are very vocal-forward, and by that, I mean the midrange seems like it has no issue keeping up with bass/treble lines. If the bass was contributing to my "lean" impression before, that is gone. Amped up a bit, the bass is strong, punchy, and very deep (track providing). Any "mid bass" it was lacking in comparison to my old phones has gone missing. Better yet, it is still wonderfully textured. The treble, which seems problematic for some, is still comfortable for me.
In short, don't let the weird frequency response chart throw you - the sound these present SEEMS flat (even if it isn't). By that I mean bass, midrange, and treble seem to have a very deliberate and pleasing balance. If anything, the HE-400 tilts toward my idea of "bright" (where bright = justice for rock type music, enough edge to be fun, not enough to be annoying). The power of the sound and the ease with which it is presented has been a revelation for me, though I've got to stop cranking up for the sake of my ears.
That said, its the music you listen to that is the last ingredient. The only thing these phones seem to do is kick butt on whatever I give them - pop, classical, jazz. They love vocal and non-vocal music. Its a great balance, especially for me - I love the comfort of Sennheiser, but find them too damn polite at times.