The Virginia gubernatorial race tarnished his image somewhat, and Democrats see him as vulnerable in 2006. They're looking for a candidate to challenge him. If they can beat him, or even give him a close race, it could hurt his presidential chances.
I don't think it tarnished him.
Kilgore wasn't attached to Allen's hip as Kaine was to Warner's.
Warner's future rested on getting his successor elected.
And Warner bowed out of the Senate race in 2006, I don't think Allen will have any serious challenge.
How did the loss, by a really poor candidate for governor, tarnish Sen. George Allen ... in a state where the governorship has long gone to the party opposite the party holding the White House?
I think that is a bit of wishful thinking.