I don’t think latency is the issue: I’m pretty sure tarsnap is just always slow. It’s a real Achilles-heel of tarsnap, and I’m kind of shocked it’s gone unaddressed so long. (Incidentally, I wrote redsnapper as a way of migrating our data out of tarsnap because tarsnap was so slow, but then once I had redsnapper, for our use case, it was mostly tenable.)
The truth is though that most de-duplicating backup solutions are also pretty slow to restore. We also just started keeping a single block-level snapshot of our data around to recover quickly in the case of catastrophes.