Let's define 'rebuilding'
It's entirely debatable what constitutes a rebuilding team, and attempts to assign some kind of cutoff, even for the sake of one discussion, are frought with problems. Here are a few possibilities to consider:
Should we examine gaps between playoff appearances? This has some merit, but if last season's Leafs proved anything, it's that teams can squeak into the playoffs without actually being very good.
Given that not a single team who has finished lower than 6th in a conference has ever won the Cup (whoops, forgot about the Kings), maybe that should be the cutoff. I mean, if you're not a contender, you're a building team, right? Well, that, or you're in the twilight years of a few stars' careers à la Vancouver Canucks... or in denial, like Calgary was with Iginla (yes, or Sundin and the Leafs). Of course, last season, the Leafs finished 5th in the East in a lockout-shortened season.
Actually, the number of teams expected to contend for a Cup (and therefore should make trades and signings with that philosophy in mind) are probably a smaller group than the aforementioned 12 teams in the top 6 of each conference. This year, we might reasonably expect Chicago, St. Louis, Boston, and maybe Pittsburgh to be the 4 teams most likely to emerge as Cup finalists. But this seems like too small a group, as there are certainly other teams knocking on the door.
The last thing to consider is the behavior of the GM. Do they add at the deadline? At free agency? Are they trading veterans away for picks? The problem here is that a lot of GMs are in denial about the state of their team and don't act according to the team's best interests per se. Also, even rebuilding teams need a few vets, so a splurge on a good player here or there isn't totally unexpected.
Essentially, we're faced with three types of problems in these situations:
1) Sometimes bad teams do well, and finish higher than expected.
2) "Contending" is also an entirely debatable term, and maybe not very relevant to 'rebuilding'
3) Sometimes teams who aren't that good also have GMs who aren't that good, and they "add" at the deadline and during free agency as though they were.
I guess what I'm trying to say is that there isn't an ultra-clear definition of a 'rebuilt' team unless they're among the league's elite, so I'll just go over some of the more obvious examples and you can have it out in the comments if you feel like adding others to the list.
Let's look at who's contending now
After the '05 lockout, the Bruins missed the playoffs twice, finishing 26th overall in 2006 and 23rd in 2007. Before the lockout, the Bruins won their division, so the lockout was really a re-boot for them. It's not like they had lottery picks, but they made a few of them count, and have only finished as early as the quarter finals once since then. This is an example of a quick turnaround. Depending on how you define it, we're talking about 2-3 years. They almost certainly didn't start with quite the same scorched Earth that Brian Burke did, but still.
In Case You Missed These Gems
In Case You Missed These Gems
The team sat in last place in their division for 4 consecutive years before climbing to 2nd place and getting beat in the first round of the playoffs back in 2007. Of course, the year after that, they made the Cup finals, and they've been dangerous ever since. Sure, their rebuild involved luck, but Sidney Crosby isn't a team, and Shero deserves credit for getting the necessary players to surround his stars to win. So for Pittsburgh the rebuild was 4-5 years.
Chicago, like Pittsburgh, had 4 terrible seasons bridging the time before and after the '06 lockout, and one where they came close to the playoffs in 2007-08. The following season, they made the Conference Finals, and they haven't looked back. 5 full non-playoff years followed by 5 seasons of competing for the Cup makes it a pretty cut and dry rebuild period - 5 years.
Now here's an interesting team. The Blues made the playoffs every single year from 1979 to 2004, and then proceeded to miss it five out of the next six years. Things look pretty darn good for the Blues now, but they were pretty darn patient in getting to where they currently are. They stocked up on 1st round picks right after the lockout and things are starting to look up. Rebuild: 6 years.
The Kings are another team that built very quietly over a long period of time... that is, until they made a gigantic splash and acquired both Jeff Carter and then Mike Richards. I guess Lombardi knew his team was ready. There is a time to make big signings and trades, and then there are David Clarkson deals. L.A. rebuild: 6 years.
The Leafs just recently passed the 5-year mark of their rebuild - that is, since Brian Burke took over. You might say they were rebuilding as soon as John Ferguson Jr. was fired, but that seems unfair to Burke, given the mess that was left. Are the Leafs behind schedule? Well, they're not late, just yet. A 5-6 year rebuild is perfectly normal, though imagining this team competing for a Stanley Cup next season is pretty difficult.
Maybe if Jake Gardiner and Morgan Rielly get a LOT better between this season and last, things can improve, but what else is going to change? A lot of players on this team are only getting older at this point, so I think some big strides are going to have to be made in the next year or ownership should start thinking about hitting the reset button.
So it's not panic time just yet, but it's not like the Leafs have a ton of time, either.