BOSTON – New Coyotes general manager Cliff Fletcher brings 25 years of experience as a GM to the table. But his hiring on Feb. 17 has afforded him exactly 25 days to perform some of the most important work of his career as an NHL executive.

With the NHL's March 13 trade deadline looming, budget issues and impending free agency may force Fletcher to deal at least one of his two biggest stars and goalie Nikolai Khabibulin, the longest holdout in league history.

"It's unfortunate that the trade deadline is so close because we have major decisions to make as to what route we want to go," Fletcher said. "We were able to do one concrete thing, getting Sean Burke signed, so we've preserved an asset there. We're talking to a lot of teams, evaluating our situation."

Rumor mill grinding team down?

The Coyotes are losing ugly. And it's beginning to wear on everyone, from the coach to the players. "That was as ugly as it gets out there," coach Bob Francis said after his team lost 7-4 to Boston on Tuesday night. "If they want to play like that, we're not going that far." It's been less than two weeks since Wayne Gretzky's ownership group took control. In that short time, the trade rumors have taken a toll in the Coyotes' locker room. Will Jeremy Roenick be traded? What about Keith Tkachuk? If salary needs to be trimmed, is anyone safe? "We're a victim of trade rumors, but about a dozen teams in the league are right now," said goalie Sean Burke, who is no longer included in that set of rumors. Burke will sign his three-year contract extension when the team returns to Phoenix after Wednesday's game in Columbus. "I don't want us to use it as an excuse. I know it's not easy and that it has crept into our game a little bit. But we have to push it aside." Pushing "it" aside isn't easy. In each city on the road, the players are asked the same trade questions. The curiosity increased in Boston because both Tkachuk and Roenick are from the area and it is where their agents met with GM Cliff Fletcher. "We've done a good job of keeping it together," defenseman Keith Carney said. "We talked about it. We can't control it; all we can control is the games."

If someone is going to be compared to an important bodily appendage, as Gretzky referred to Fletcher when he said Fletcher was his "right arm," it's obvious that Fletcher and Gretzky plan to work closely over the next two weeks, a period which likely will have a huge impact on the team's future. Fletcher and Gretzky talk daily, even when both are on the road. Gretzky is no micro-manager, but Fletcher's isn't working in a vacuum.

"When I get back, we'll sit down and analyze it all and see if we're going to do anything next week," Fletcher said.

One week. That's all the time he has to decide the futures of Jeremy Roenick, Keith Tkachuk and Khabibulin.

Fletcher is attempting to re-sign Roenick, who is due to become an unrestricted free agent this summer. Fletcher met with Roenick's agent, Neil Abbott, in Boston on Tuesday, but no numbers were exchanged. According to sources, Roenick may be asking upward of $7.5 million, roughly $1.5 million more than the Coyotes are willing to spend.

But if Roenick is re-signed, Tkachuk, with his guaranteed $8.3 million salary, might be traded. Tkachuk will become a restricted free agent at season's end. Because he makes more than the league average of $1.4 million, the team needs to make a qualifying offer of at least $8.3 million to retain his rights. While in Boston, Fletcher also met with Tkachuk's agent. The meeting was meant to update Tkachuk's representatives on the team's strategy -- namely, that it will deal with Roenick's camp first.

If Roenick doesn't sign, Tkachuk likely will be traded so the Coyotes can get something in return for him.

"I guess the most important thing is J.R., only because he can potentially become an unrestricted free agent at the end of the year. We have to see where the lay of the land is there," Fletcher said. "After that, there is nothing else that is pressing because we have the rights to all these players, and there is no internal pressure to make trades before the deadline. If there's something there that we like, obviously we'll move on it. If there isn't, we're fine."

The other issue is what to do with holdout Khabibulin. The Coyotes hold his rights, but his value is highest now. They could sign and trade him. However, it's doubtful the cash-strapped franchise would assume the burden of another $4 million investment in a goalie and then have the pressure to move one of them.

But one thing is for sure: Fletcher will go for the best deal possible.

"We would go where the best deal was, East or West," he said. "It's part of the challenge of building a winner."

And building a winner is the reason Gretzky hired Fletcher. Since it was such a foregone conclusion that Cliff Fletcher was going to play a major role in the Wayne Gretzky era of Phoenix Coyotes ownership, the assumption was that Fletcher and Gretzky were close friends.

Signing Burke

When Wayne Gretzky's ownership group took over, Cliff Fletcher and Gretzky entered into talks with both Sean Burke and Nikolai Khabibulin at the same time. "When we took over operation of the team, basically we called both agents at the same time," Fletcher said. Obviously, signing Burke was more feasible financially, and Khabibulin wasn't budging on his $4 million stance. Khabibulin turned down a three-year, $9 million deal last year. But that was a deal Burke took with pleasure. "I said at the beginning of the year I wanted to make their decision difficult," said Burke, who signed a one-year contract to return to the Coyotes just before the season began. "I felt I did that. If they could have signed Nik to a reasonbable amount of money, they might have done that, too. But all I know is that they stepped up and signed me to a nice deal and I'm going to work hard for this team."

But Fletcher said the two men didn't have much of a relationship before Fletcher was hired by Gretzky.

"I never had a real close relationship with Wayne prior to the opportunity to talk about coming here," Fletcher said. "We had that rivalry when I ran Calgary and he was in Edmonton. And when he was in L.A. and I was in Toronto, we did talk at one stage about the possibility of him coming to Toronto as a player before he went to the Rangers."

Back in Gretzky's early years playing for the Oilers, the two men viewed each other from a distance. Fletcher was the long-time general manager of the Flames, and Gretzky was making history for the provincial-rival Oilers. Gretzky won a lot of the battles, but the way Fletcher carried himself and ran his team apparently were never lost on Gretzky.

Of course, the Flames didn't have the same success as the Oilers, who won four Stanley Cups with Gretzky, but Fletcher's Calgary teams went to the finals twice and won the Stanley Cup in 1989. Fletcher also was successful as GM of the Maple Leafs from 1991-97.

"I was flattered by it and excited by another chance to build a winner," Fletcher said of his opportunity to work with Gretzky.

So now, several years after they represented opponents, it's totally different. They're partners in the hockey operation of the Coyotes, and both charged with the responsibility of cutting payroll and making the team better -- all in less than 25 days.

Brian A. Shactman covers the NHL for ESPN.com. He can be reached at brian.shactman@espn.com.