This is completely not surprising to me.
Evolve makes it sound like these are new mutations. Not usually. They just are present in a very small percentage of a given group of microbes. Nature keeps around a lot of potentially useful things in genomes by having them only present in fairly rare individuals of the species. That way, the cost of keeping them around is low in terms of genome space and energy to replicate them/produce the relevant proteins.
Bacteria use a trick called horizontal gene transfer to quickly spread things that turn out to be useful (example: antibiotic resistance) to much of the population and even to other microbe species.
As to the universality of bugs being able to in time to find a way to break down almost anything, look at the work of, for example, Terry Hazen at DOE and the University of Tennessee on using bacteria in hazardous waste site cleanup.