@ematsen, @cwhidden : Running under MCMC under the prior to sample from a diffusion on tree-space sounds like a great idea. BEAST, MrBayes, and RevBayes would all work nicely for this. Feel free to email if you'd like help doing this through RevBayes.
One thing to consider is SPR may be applied without constraint on an unrooted tree. For time trees (rooted trees with branch lengths proportional to time), whether a branch is a valid regrafting point depends both on the subtree's ancestor's age and the start and end age of the receiving branch. e.g. A subtree with age 100 cannot regraft to a branch originating at age 1.
So SPR proposals for time trees often impose additional constraints on regraft points (see fixed node-height prune regraft, FNPR), or impose constraints and resample the attachment node's age (Wilson-Balding). For more, see Hoehna, Defoin-Platel, and @alexei_drummond's work on tree proposals. You can imagine other types of SPR proposals that produce valid states for a time tree, some of which would perform poorly in practice, but I wanted to mention that the type of diffusion you impose on time-tree-space will interact with your prior distribution on divergence times. Of course that might be exactly what you're interested in!