Tens of millions of years isn't no time at all biologically. I don't think that is quite true that all phyla originate in the Cambrian, I'd have to check, but I agree many phyla do originate in the cambrian. Don't get over hung-up on the phyla thing anyway. The importance of phyla is retrospective. At the time the difference between one phylum and another would have been very small, just like modern speciations, its just that subsequently they ended up going different ways that formed different branches of the phylogenetic tree.
From The List-O-Links:
WHAT ABOUT THE CAMBRIAN "EXPLOSION"?
Another service of Darwin Central, the conspiracy that cares.