I believe I saw a reference recently saying it only took 40million years before cellulose became widespread biodegradable. I can't find a source for that number, though it looks like it might have been an MS mycology student circa 2014.

http://hn.premii.com/#/article/15977640

I suspect plastic will take significantly less time than cellulose though. It's an amazing material, and the biodiversity of the planet (though shrinking) is still much higher than it was when cellulose began proliferating.