That woulda/coulda been epic... The "four-eyed" eastern dude up against the local machine. It sounds the story nugget for 25% of all of the westerns ever made; except this would have been for real. Both MacKensie and Roosevelt understood the higher levers of power, and used them. If that would have worked out to the Hollywood ending, that might have guaranteed Teddy the White House, with or without the Rough Riders experience.
Well, I only have two caveats. The first being that TR was completely willing to use the boss in New York, until such a time as he was in the governor's mansion and could move against him. It is likely that Roosevelt would use a sinilar tactic against Mackenzie if he could; not make any overt moves until he was secure and then work against him.
Secondly, although a Senator of the era had a good deal of patronage power, Roosevelt was never a LaFollette; i.e. he never seemed to have the same Passion, or ability to use patronage and politics to build up a counter-weight to the bosses' machines. He was always much more comfortable going to the people and putting pressure on the elected officials that way. As a Senator, he would likely have less opportunities to do this than if he were a governor.
Now, although I doubt we would ever see Roosevelt as a Populist (that man was a loyal Republican, especially during thia point in his life), he would likely emerge as one of the great reforming voices in the state and would be one of the first Progressive leaders in the region. As such, it would be interesting, but I could see him and Bob LaFollette being natual allies (and, yes, the irony of those two getting along ...). On the state side, I could see him becoming close to other young reformers such as Usher Burdick. Actually, a Rooaevelt-Burdick friendship would be awesome! (Burdick was a fascinating customer in his own right, and pretty damned rough and tumble when he had to be)
Interesting enough, I wonder if a Senator Roosevelt would be aligned or opposed to the Nonpartisan League when it emerged (if it did). My gut says that, even if he was sympathetic to the NPL, he would be turned off by the leadership and the covert (sometimes overt) Socialist leanings of said leaders. And, of course, this leads me to wonder how TR would view good ol Wild Bill Langer (the only sitting governor to try to declare his state its own country after the Civil War

. Ah, Wild Bill. Definitely the Starscream of the NPL!)