Russel is correct, the W.E. takes you over Carson Pass and right past Kirkwood, a ski resort. You get up to about 8700 feet. May would be about the earliest I would try that, and you could still get serious weather then. Also, much of the trip across Neveda is at elevations over 5000', and it get's cold and windy there.
I was at the South Rim of the Grand Canyon on New Years day 2005 (not by bike), and it was snowing.
while it's an exaggeration to say it rains every day north of SF in the fall (i live in the SF area), it is true that as you proceed north, there is more rain. you may get nice weather on the coast in winter, but when a winter storm comes through, it rains hard and is cold.
I wish it was different, but bike touring in winter in the US is not very friendly. Oh, and don't foget about the really short days. There's a lot of tent time if it gets dark at 4:30pm and doesn't get light again until 7am.
If your timeframe is truely fixed, Feb-Mar-April are perfect touring time for the southern hemisphere. New Zealand and Australia would be more fun. (Yeah I know, hideously expensive plane ticket.)