Bill Richardson has been a fixture in New Mexico politics for 25 years, but the state is still getting used to him. New Mexico has always been, politically at least, a rather sleepy sort of place. Richardson, a former Democratic congressman who also served as Bill Clinton's U.N. ambassador and Energy secretary, is an intense and impatient man accustomed to taking on more tasks than any mere mortal (including himself) can possibly see through to their end. But in his first few months after taking office as governor last year, Richardson bent the state to his style rather than the other way around. He pushed through more legislation than any of the 23 other statehouse newcomers elected with him in November 2002.

Some of it was a matter of luck. New Mexico, although 47th in per capita income, is rich in oil and natural gas and has a tax structure that covers service industries. As a result, the state was one of only three in the country to enjoy a surplus last year. What's more, Richardson was following a predecessor who vetoed more than 700 bills; there was a good deal of pent-up legislative demand.

Richardson didn't squander a minute. He didn't even wait until his inauguration to begin his sales pitch for his programs and for the state. The day after his election, he got on a plane to jawbone tech executives in Silicon Valley. "Frankly, we haven't had that kind of ambassador for the state for many years," says J.D. Bullington, lobbyist for the state chamber of commerce. "He's not really a New Mexico Democrat; he's an international Democrat."

If Richardson had an advantage in the state's relative fiscal health, he also knew how to press his advantage. He made it clear from the start that he wouldn't accept inertia as a reason for not trying new things. Within a few weeks after taking office, the new governor had persuaded the legislature to slash the top income tax rate by 40 percent and capital gains taxes by half, restructure school financing and the educational bureaucracy, stiffen drunk driving penalties and approve gay rights legislation that had languished for a dozen years. "We got about 97 percent of what we asked for," the governor says, smiling.

Richardson has lured movie shoots to the state with an $85 million investment fund, and managed to double the state's trade with Mexico, using his international connections to strike up a relationship with Mexican President Vincente Fox and bringing Fox to Santa Fe in November. Richardson proudly boasts he calls CEOs on a daily basis and "sucks up to them big time."

He was a fixture on the national news all throughout 2003, negotiating with North Koreans about nuclear weapons a few days after taking office, trading on his federal experience to comment on national television about Iraq and the Northeastern blackout, appearing regularly with prominent Democrats by hosting a debate among the presidential candidates and preparing to chair the party's national convention. "He just seems to be everywhere addressing everything," says Maxine Velasquez, vice president of a communications workers union. In New Mexico, few have seemed to resent Richardson's national profile. His most recent approval rating in a statewide poll was 64-19 in his favor.

But if Richardson's popularity among the voters has held up, his Midas touch may be wearing out. Everyone knew that the long parade of victories couldn't possibly go on forever. Sometime during the fall, the mood in the legislature seemed to turn against Richardson's activism. A package of tax increases, proposed to make up for some of the revenue lost to the tax cuts earlier in the year, went nowhere at all. It was a major embarrassment. Legislators worried that his tax and spending proposals would cost too much down the road. Even with its mineral tax windfall, the state is looking at a shortfall of at least $58 million going into the new year. Asked whether Richardson's honeymoon is over, House Republican Whip Joe Thompson jokes, "we're at the very least on the flight home, and there may be some counseling."

The special legislative session called by the governor to pass his second tax bill began--and ended--without much consensus among legislators on what needed to be done. In fact, there wasn't even a bill until after the session had already started. Richardson acknowledges that he didn't do a good job selling his tax plan. And selling it isn't going to get any easier this year. Legislative leaders have already signaled they won't be interested in raising taxes. "You can't make up $350 million"--the revenue lost in the earlier round of tax cuts--"unless you have major tax reform," says Bullington, the business lobbyist. "Someone's ox is really going to get gored."

Richardson's aggressiveness was clearly an asset during his initial months in office; by the end of his first year, it was being talked about as a weakness. The governor angered legislators when he spent the state's $60 million in federal bailout funds without consulting them. Then, in October, a profile in the Washington Post recounted the way he demanded that state troopers "hurry up" as they drove him to his next event at speeds reaching 110 miles per hour. Richardson apologized.

But by that time, it was becoming common around the capitol building, known as the Roundhouse, to hear the governor described as high-handed or referred to sarcastically as "His Eminence." Even loyal Democrats are wishing Richardson, after all the bills he pushed through at the start, would reach for the brake pedal. "We've been on a whirlwind type of ride with this governor," says James Taylor, the House Democratic whip. "We're going to need a break at some point and look at whether what we've done is working."

That would require New Mexico's governor, accustomed to a frantic D.C. pace, to slow down to the Santa Fe rhythm. Even some of Richardson's business allies, who cheered his tax cuts and education changes last year, now say it is all too much to take in. Bullington, of the state chamber of commerce, warns that the governor's attempts at health care reform are "a little too fast-paced for some of us."

At the same time, there is the danger of losing legislative support. Some legislators complain that Richardson's methods of negotiation have been disrespectful and occasionally personal. The governor himself concedes he's "bruised feelings" along the way. "We in the legislature have the power to say 'no' to anything," says Max Coll, chairman of the House Appropriations and Finance Committee. "Pretty soon, we'll have the wagons circled and we'll protect ourselves against these tactics."

The governor joked early in his term that dealing with the New Mexico legislature "may be more difficult than the Iraqis or North Koreans." If Richardson is to avoid the path taken by other members of his gubernatorial class, scoring political points at the expense of closing deals, he may have to slow down a little in order to convince legislators to keep moving. "The wheels of state government are sometimes slow and he is impatient sometimes," says state House Speaker Ben Lujan. "We need to catch up."

Richardson himself worries that the sudden revenue shortfall and the growing reluctance of legislators to get with his program add up to the same sort of policy stagnation that has marked other states recently. "Some of my strongest resistance to change has been from entrenched Democrats," the governor says.

But Richardson is far from finished. Although he didn't get his tax package through last fall, he plans to try again this year. The same special session that brought him defeat on taxes handed him victory on a tough sex offender law and enactment of a $1.6 billion transportation package. Now he wants to extend health coverage to the state's uninsured through an expansive pooling program similar to the one created last year in Maine at the behest of Governor John Baldacci last year.

"He's the most ambitious and aggressive governor we've had recently," says University of New Mexico political scientist Gilbert St. Clair, "and probably ever."