I've worked on several projects where we were simultaneously developing the mechanics and levels,  but this was usually because of time constraints which limited our options.  We did our best to work on them together and ensure that they were cohesive in the final product but there were always issues.  I think this was mainly because of a lot uncertainty (for both system and level designers) and hesitation to make major changes for fear of causing work to the other party.  So, ideally one will be nailed down first...but which one?  I'll preface my answer by saying that my background is in level design, so some might consider my view to be a bit biased :)

In an earlier post I talked about how a common theme with Mario games is the mechanics and how it feels to play as Mario. Jumps, run, etc all have a unique feel that to some extent are present in all of their games.  The levels change drastically throughout the games (even within each game) but those levels would not be possible or nearly as fun if they didn't have the foundation of Mario mechanics to build on.

A Level Designer is at his best when he knows exactly what he has to work with and can iterate on the layout based on fun and feel instead of any time spent guessing.  Something as simple as a change in movement speed of an enemy or even the player can have a huge effect on the flow and pacing of the level...and even it's function.  More drastic changes, for instance the movement type of an enemy from ground based to flying or leaping, can invalidate every piece of cover in a level...or the cover system entirely! 

Level Designers that have at least the core mechanics nailed down for them early in their level design process have the ability to build an entire experience and fine tune it from the start.  When they don't have this, they end up making broad strokes in the beginning so they can adjust for any changes that are coming and then spend their iteration time changing the level with the evolving mechanics instead increasing the fun factor and adding memorable moments into each encounter.

In order for this method to work there has to be support and understanding from everyone on the project.  There must also be a very clear design before the first work begins so that everyone understands the vision and can lay the ground work quickly.  The System Designers have a very difficult job early in the process and there's a huge burden on them to prepare for everything to come.  They have to make guesses based on what they think will be fun and be given the freedom to make rapid iterations early in the development cycle.  There will be lots of trial and error as early ideas don't pan out...but when that happens before levels are made it's much less impact on the schedule.

The games this method is easiest to use on is sequels where there is already an established mechanics system and it can be built upon.  The early time can be spent honing mechanics that fell short and establishing a few new things to make the sequel unique.  I strongly believe this method should also be used in any project even though it may be more difficult in the beginning and slower going.  The benefits you'll see from heading into level design with mechanics in place is astounding.  But the key, is that it allows any future iterations to be focused on making the established game play better...instead of trying to just make it function.