Can we be sure that Cuomo would win in 1994, even with Bush in the White House? Yes, it's true that his loss was pretty narrow in OTL
http://en.wikipedia.org/wiki/New_York_gubernatorial_election,_1994 and that it was based partly on the unpopularity of Clinton and the Democratic Congress in 1994. Yet in part it was also based on his administration having had some wear and tear after a dozen years in Albany. One should note that even in 1990, Cuomo only got 53.2% of the vote (though he won easily because of divided opposition).
http://en.wikipedia.org/wiki/New_York_gubernatorial_election,_1990
Even if Cuomo wins in this alt-1994, if he just squeaks through with a narrow plurality, that may lead to some skepticism about his electability in 1996.