There has to be synergy/cooperation between ownership, GM and head coach. Look at the Patriots when Pete was there: Kraft didn't know what it took, and he allowed the players to run between Pete and the GM whenever they didn't like something. Pete also had no say in who his players were. After Pete was fired, Kraft hired Belichick, let Bill do what he needed to do, and voila! Likewise in Seattle now, Pete was brought in specifically to install his philosophy throughout the organization (not just with the players). He had input into who was hired as GM. He and John Schneider work hand-in-hand, and Paul lets them do their thing.
Someone earlier in the thread mentioned that Dallas had had a lot of talent. All the talent in the world won't help if they can't learn to play together as a team. That may or may not be an issue right now, but it's something to possibly look at. Sometimes with lots of talented players you end up with lots of egos. It takes a strong leader/diplomat to bring those guys together (think Phil Jackson in Chicago and LA). And again, that coach has to have the full backing of the GM and owner or he gets undermined.