RICHARD NOTEBAERT IS THE FIRST TO ADMIT that Qwest Communications was a mess when he was asked to step in as chairman and CEO in 2002. In fact, it was a much bigger mess than he knew when he accepted the job.

“It's like that Toby Keith song, ‘I wish I didn't know now what I didn't know then,’” he said with a laugh. “At the time I accepted the position, many of the things that came to light later were not known. Those items, such as the [$2.5 billion] restatement, came to light later.”

Notebaert succeeded the now-indicted Joseph Nacchio as head of a company that was spiraling downward. The combination of Qwest, a company that invested billions in building a national fiber-optic backbone just before the telecom bubble burst, with US West, the 14-state former Bell company with customer service problems of its own, had created a telecom monster that many thought couldn't be tamed.

Four years later, Notebaert has done what many thought was impossible: Through disciplined management, including judicious cost-cutting, he brought Qwest back from the brink of bankruptcy and all the way to where it stands now — the brink of profitability. In the first quarter of 2006, the company not only recorded positive earnings per share of 5¢, substantially exceeding analysts' estimates, but said it was on track for profitability for all of 2006.

As a result of the first-quarter results and projections, Friedman Billings Ramsey revised its 2006 full-year earnings estimates for Qwest from 3¢ per share to 27¢ per share.

In addition, Notebaert has helped repair Qwest's relationships with its customers, the communities it serves — especially its hometown of Denver — and, to some extent, state regulators. Qwest has actually built up enough momentum within the investment community that its stock is trading at a higher premium than those of other former Bell companies — a fact that, in the long run, might not work in Qwest's favor.

“I think the management team has done an excellent job, comparing where the company was when they arrived to where they are now,” said Christopher King, a financial analyst with Stifel Nicolaus & Co. “They have staved off bankruptcy fears and managed to hold revenue in place, if not grow it slightly to drive free cash-flow generation despite a tough telecom environment. I think Notebaert has done a masterful job.”

However, King and other analysts are quick to add that Notebaert's biggest challenge is yet to come. Without a wireless company of its own, and without the major IPTV push of AT&T and Verizon, Qwest has fewer growth opportunities at the same time it will be facing a major challenge from Comcast's newly aggressive voice-over-IP push.

“Comcast's footprint overlaps about 50% of Qwest households,” said Donna Jaegers, Denver-based analyst with Janco Partners. “With Comcast finally getting more aggressive rolling out digital phone service, Qwest may see a lot more attrition in voice lines this year. Plus, the company is dragging along a lot of baggage, including the poor track record they had with customer service. It is going to be a challenge for [Notebaert] to hang on to his consumer customer base.”

Notebaert's one notable failure — Qwest's inability to wrest MCI from Verizon — also factors into concerns about the company's growth potential going forward.

ASK NOTEBAERT ABOUT QWEST'S FUTURE, and he talks about its people. He came to the company after 31 years in the Bell family, including five years as chairman and CEO of Ameritech, eight months of retirement (which he hated) and two years at the helm of equipment manufacturer Tellabs.

“One of the reasons I came was the opportunity to relate to employees that probably somebody from outside the sector wouldn't have had,” he said. “My friends' reaction was pretty consistent,” Notebaert said. “‘Are you crazy?’ ‘What is wrong with you?’ But to have the chance to come back and operate a huge company like this one was an opportunity I couldn't pass up.”

Two weeks into the job, that opportunity already was losing its appeal, he said. The intent to restate Qwest's 2000 and 2001 earnings was announced July 29, 2002, 41 days after Notebaert took over. Investigations by the Securities and Exchange Commission and the Justice Department, as well as state regulators, would follow. It would take until October 2003 for the dust to settle on the $2.5 billion in additional losses to be announced.

“I wouldn't wish on anyone going through the level of restatement and the challenge of federal and state agencies that we faced,” Notebaert said. “We lost a year and a half. But the team has done a fantastic job. It's just taken longer than I thought it would.”

Disciplined spending has been a hallmark of the Notebaert regime. Operating expenses declined almost 4% between 2004 and 2005 and another 5% between 2005 and 2006. By replacing $3 billion in high-interest debt with lower-interest notes in 2005, the company also significantly reduced its interest expense.

“Dick did a lot of cost cutting,” said Rob Reuteman, business editor of the Rocky Mountain News since 1997. “He reduced the debt load from $26 billion by selling off some fairly substantial revenue-producing assets such as the directory business. So while they have been able to reduce their debt, it's come at a price.”

Qwest has also sold off wireless assets and spectrum, including last year's sale of its PCS licenses in the 1900 MHz spectrum along with its cell sites, wireless network infrastructure, site leases and associated network equipment to Verizon for $418 million. Since 2003, Qwest has been reselling Sprint wireless services.

BUT THERE ALSO HAS BEEN a focus on improving employee morale and customer service, two areas where Qwest suffered mightily.

“The company's service reputation with its customers was not very good, the reception by customers was not very good and the morale of employees was pretty low,” Notebaert said.

In 2002, Qwest was dead last in the University of Michigan's American Customer Satisfaction Index, with a score of 56. The other major telecom service providers' scores were clustered in the low-70s. This year, Qwest finished fourth, behind Cox, AT&T and BellSouth (and ahead of Verizon) with an ACSI score of 70, only one behind the two telcos tied for second place. (Cox scored 76 to lead the fixed-line service provider category).

Notebaert has repeatedly stressed his company's determination to meet industry benchmarks in categories such as DSL penetration, long-distance sales and revenues, saying the ability to meet those industry benchmarks is a $500 million revenue opportunity for Qwest. Doing this means basic blocking and tackling, he said.

“The question is, can this team, this group of people, execute?” Notebaert asked. “Can they take an order, not have a billing problem, deliver the service when we say we will, have a smile and live every minute as if the customer is the center of the universe? What we've been able to do so far is a tribute to the employees, as they feel the flywheel of success. It's a very disciplined process. I do an all-employee call, and we talk about it all the time.”

Notebaert has also done much to improve Qwest's standing in the community, Reuteman said. Whereas Nacchio shut down the US West Foundation, a community-enrichment program, on the day he took over the company, Notebaert has reinstated it and is personally involved in community activities.

“When they brought Dick in — he is a real Boy Scout, compared to Nacchio,” Reuteman said. “He is really a good guy. He has become pretty established in the community, involving himself in non-profit groups. He has restored their commitment to corporate responsibility. I'm not aware of anybody who is an enemy of his or critical of him.”

WALL STREET RARELY CHECKS THE PUBLIC SERVICE RESUME of a CEO, however, and although Notebaert is clearly respected for everything he's done so far at Qwest, the analyst community isn't convinced he can pull more rabbits out of his hat.

“He's got a lot of challenges,” said Janco's Jaegers, who has a “sell” rating on Qwest stock. “Their stock premium is at the high end of the regional Bells, even though they don't have a wireless company, they don't have a Yellow Pages subsidiary that generates revenue and they haven't made much of an investment for IPTV.”

Because of Qwest's stock premium, she adds, the company is not even an attractive takeover target.

“I don't think anybody will touch them until they see how Qwest will defend itself against Comcast,” Jaegers said. “In the second half of the year, everyone expects Comcast to get more aggressive, and if that starts to get reflected in Qwest's stock price, then maybe other new carriers like Embarq or Windstream might be interested in merging with them.”

Notebaert's conservatism could come back to bite Qwest, analyst King said.

“He's an excellent manager, but if there is a criticism of him, it is a history both at Ameritech and possibly at Qwest of under-investing in the telecom plant,” he said. “His hands are tied on a lot of that. Given their financial position, capex is going to have to be minimized to a large extent.”

The bigger issue, King said, is lack of revenue-growth possibilities.

“This is going to be the biggest challenge the company faces,” he said. “They have made some great strides over the last couple of years. Their growth profile in terms of free cash flow and operating cash flow look better than their counterparts, but they started from a lower point, and to a certain extent, there was a lot of low-hanging fruit in terms of getting costs out of the business and getting interest expenditures down. A lot of that low-hanging fruit is gone. Does 2007 look significantly better than 2006? I don't think so.”

Notebaert believes Qwest's ventures into things such as video are being sold short because the company is avoiding hype.

“Are we doing fiber to the premises? Yes, in greenfields,” he said. “Are we pushing bandwidth out? We've been at five [megabits per second] for two years. Everyone else is catching up. I see stories that a company is cutting its DSL installation response interval to five days, and I smile to myself because we do it in three days. We are looking at IPTV in our labs because we want to understand it. But we don't announce things until we do them.”

Qwest continues to operate the video-over-copper deployments that US West pioneered in Scottsdale, Ariz., and in suburban areas of Denver, but hasn't expanded those.

The company also recently bought OnFiber, a metro Ethernet provider, and extended its out-of-region reach and its revenue potential.

Analyst King believes the company will have to continue to expand, either as a buyer or a seller, to find growth opportunities.

Notebaert is standing firm with the current strategy, however. He told analysts at the May Lehman Brothers conference that the company is making more money selling wireless services now than it did when it owned — and had to invest heavily in — wireless infrastructure. The company is seeing growth, he added, in selling services on its national multi-protocol label switching network, in its wholesale operation and in data services within region.

Qwest is on track, Notebaert said, and points to his track record.

“Everything that we say we will do, we've done,” he said.