With free agency, 12 team playoffs, and the general balance of the league, the fact that the Lions and Bills are the only 2 teams out of 32 to not make the playoffs in a decade speaks volumes about the organization's commitment to putting a winning product on the field. The big changes since the last Bills playoff team have been
firing John Butler (who took most of the scouting department and front office with him) and complete overhaul under TD
firing Tom Donahoe with temporary hiring of Marv Levy, Dick Jauron
firing Dick Jauron with promotion of Buddy Nix and ?
It's probably not just a coincidence that the first bullet -- which amounted to gutting of the FO and coaching -- has had far more impact (for the worse) than the other two "shake ups", which preserved the majority of the structure intact.
Sometimes patience is just a polite way of saying there is a stubborn refusal to admit that the status quo isn't getting it done.
Edit: At least with the Lions, the firing of Matt Millen (precipitated by Bill Ford publicly saying he'd fire Millen if he could) could be seen as a move in a different direction for Detroit. In the Bills case, the change was a bit of musical chairs with titles.
The Bills and Lions, by the way, both blew it up the same year, hiring Donahoe and Millen, resp.