Question: I'm aware that our earliest records of many major animal and plant phyla come from the Cambrian or Precambrian periods, and I'm also vaguely aware of some of the objections raised with general concept of phyla. With this in mind, I'm curious which of widely accepted biological phyla appeared most recently, and what evidence do we have of their relatively recent appearance? 

I'm most interested in animals, but I'd also welcome any information about other organisms.

Answer: 
In my view, we simply don't have good enough data to answer this question. The fossil evidence is too sparse prior to the Cambrian and the evidence that we do have suggests that the phyla were already too separated. Meanwhile, the depth of time and the different lifecycles and circumstances of the species involved mean that any "genetic clocks" we might use are likely to be too poor at keeping time and, indeed, different attempts have delivered different estimates of the time of divergence.
As far as I know there is no phylum which appeared after the Cambrian. Every discussion beyond that is close to speculation, as the divergence estimates of different studies vary significantly. 
You might want to look into one of the resources mentioned below:

* <http://www.timetree.org/index.php>
* <http://www.onezoom.org/>