I went across the 'Zilov gap' (be aware no one in Russia calls it this) in late October - it wasn't that bad a time to be there, but might have been due to a later than normal winter. Damn cold but water levels at the bridges (most of them on the new road are still under construction, there is always some kind of bypass road) were lower than what it sounded like in summer. I think the best time conditions wise would be early fall. The amount of people driving Japanese cars back from Vladivostock at the time seemed to confirm this.
I used part of the new road and parts of the old road as the locals directed me...this is one country where you NEED to speak some of the language. Talk to the drivers of the Jap cars, the guys working on the road are trucked in and trucked out, and often know very little about what is going on past their own worksite. They have their own diesel dumps so don't need to know about petrol. They didn't tell me which roads I wasn't "allowed" on, just interesting facts like there wasn't petrol for 600km (the next fillup point was 40km away and had been there for years). There were "no entry" signs on some sections but like most roadsigns in Russia they refer to an imaginary concept only.
The signs I saw said something about 2003 completion...while this might be ambitious there are a LOT of people out there working on it and some sections are ready to be paved now, so not sure how long it will stay dirt anyway...