Some folks get in the trail in late May but I DO NOT recommend it if you're planning to come from far away. There's always a chance of snow and at least wet conditions that most of us like to avoid.
Our efforts at maintaining and keeping the trail open are jeopardized if we use the trail during wet conditions. Don't do it, please. Go in the summer time. You'll have more fun and do no damage. Further, be sure to check with the FOTR list or http://www.pirate4x4.com, Rubicon Trail Talk forum for more on court (lawsuit) issues or trail restrictions
NOTE for 2008 and beyond: the current Eldorado National Forest Record of Decision (Final EIS) calls for Winter Closures (total) from January through March -- meaning no winter travel by wheeled vehicles except over pavement areas.
Go here for more on how to get involved in land use in general.