"What you see is what you get"

This nod toward a political center, observers say, smacks of the sort of thing Richardson's friend and political mentor was so good at. "If anyone could have been a tutor for Richardson, it was Bill Clinton," says onetime Richardson opponent Sanchez, who, after losing the governor's race, helped coordinate the successful Bush campaign in the Southwest in 2004. Sanchez recalls watching Richardson, on the campaign trail, pick up Republican issues such as tax cuts and run away laughing with them.

"He is a very deft, very savvy politician," Sanchez says. "He knows how to relate to people just like Bill Clinton" does. Picking up issues that might resonate with swing voters, Sanchez says, is an example of Richardson's "learning from the master."

But Richardson has a knack for self-promotion that is more naked. In 2003, after the successful passage of a series of income-tax reductions, Richardson's administration took out a full-page ad in the Wall Street Journal, supposedly pitching New Mexico's positive business climate but also featuring a thoughtful Richardson. "A Democrat cutting taxes?" the ad read. "Things are different in New Mexico."

Ironically, the picture in the ad was a file photo from one of Richardson's darkest hours, the late-1990s debacle over Los Alamos National Laboratory. When the federal weapons lab became known better for security breaches and wayward scientists than for smart nuclear research, Richardson was at the helm of the Energy Department. During those grim times Richardson sweated under merciless grilling from Congress about the way he ran -- or didn't run -- the agency, and about the persecution of scientist Wen Ho Lee. By the time the 2000 presidential race was up and running, Richardson's political star had been dragged out of the firmament. He went from a likely V.P. candidate for Al Gore to a political footnote.

"That knocked him right off the Gore ticket," Atkeson, the political science professor, says. "To the best of my knowledge, that's his biggest political liability."

Whether the issue would dog him in a presidential race remains to be seen. While leaking government secrets has hurt a household name like Karl Rove, the American public has yet to seize upon it as a voteworthy issue. It's likely that by the time Richardson starts pushing hard for a slice of the limelight in 2007 or 2008, the question of Lee and his secrets will be almost forgotten.

Nowadays, Richardson is ascending beyond New Mexico again, including well-publicized trips to New Hampshire. James Pindell, of the political Web site PoliticsNH.com, says Richardson is ahead of any of the other potential 2008 contenders in the number of New Hampshire visits this year. Senate Majority Leader Bill Frist has made two visits. Sen. Hillary Clinton has also made two. Richardson? Three, so far.

"Most of these people come in, they do their speech, and they're outta here," Pindell says. "He spent two whole days."

Richardson admits the trip was a bit of a 2008 tester. "I wanted to get a good lay of the land," he says. "I felt very good. I got good response."

What Richardson did in New Hampshire is something he's known for coast to coast: hobnobbing with his inner Rolodex on turbo. From D.C. to Los Angeles, Richardson seems never to be in a crowd of complete strangers. Somehow, from behind the microphones and lecterns, he'll spot a familiar face, dredge up the person's name without a staffer to whisper it to him and go so far as to shout out to the person, who invariably reacts with flattered surprise.

"He just walked around the crowd, and he would just recognize people," Pindell says. "You can't make this stuff up."

Candidates, even nondeclared ones, have three things to accomplish in a New Hampshire trip, Pindell says: Introduce yourself to the nation's early primary voters, leave the crowd with a better opinion of you than when you arrived, and show a little respect for the East Coast traditions of politics and baseball.

"While he appears intelligent, he was more than happy to be in New England and talk about the Red Sox," Pindell says. "People seem to be very impressed with him."

All of the gallivanting about has helped wedge Richardson back into the limelight. He has even gotten the sideways compliment of being spoofed on "Saturday Night Live." In March, "SNL" player Horatio Sanz played Richardson perfectly, with the coiffed black hair, imperious public persona and black suit. In the skit, which features several other politicians, Sanz/Richardson tries to explain to Barry Gibb of the Bee Gees, played by Jimmy Fallon, that he loves their music. Fallon/Gibb responds by screaming at him.

Richardson's response to being played so well by an actor he refers to as "that fat guy" was to send Sanz a New Mexico pin with a note. "I said, next time, wear this -- at least you'll have something nice to wear," Richardson recalls, chuckling.

Two things other than appearance ring true in the skit. First, Richardson genuinely loves cheesy classic rock. He makes a habit of attending the acts that show up in New Mexico stadiums, including Cher, Ringo Starr and Julio Iglesias. Invariably he'll meet with the stars. For a time, while governor, he held a membership in a local Jimmy Buffett fan club.

Second, Richardson is no lightweight. He is a big guy who knows it. Since becoming governor he has taken to the bicycle to try to keep in shape, puffing up and down bike paths in Albuquerque with friends and security guards whenever he can. When I joined him on one of these excursions, I clocked our average speed at about 10 miles per hour. Nonetheless, he rode for about 13 miles, chugging along slowly in a sweat suit and Lance Armstrong-esque wraparound sunglasses.

If Richardson decides to run for president, he will not have the heartwarming military story of Sen. John McCain. Nor will he have the catalog-perfect children of Sen. John Edwards (Richardson and his wife, Barbara, have no children) to trot along the campaign trail. Which doesn't seem to matter to Richardson: "I'm not going to try to weave in anything personal," he says.

What Richardson needs now, observers agree, is more exposure of the North Korean and New Hampshire kind. Otherwise, he risks being merely an interesting sidelight to attention-grabbing potential candidates like Sen. Clinton. "He's the girl at the dance who hasn't been seen by many of the guys," Monahan says.

Comments like this make Richardson chortle. "My approach is going to be: Here I am; this is me," Richardson says. "What you see is what you get."

• View blog reactions