It would take a little work to put together serialization routines for Set::IntervalTree and Storable to play smoothly together. That may be worth it if you're going to make heavy use of this, but a quick workaround is to write specialized serialization and de-serializetion routines good enough for your own code and use those convert from a hash of objects to a hash of strings and back. Then you can use Storable on the hash of strings. It sounds like you're thinking along these lines already.

One advantage of this approach is that if you decide to do the more general job, you've got some prototyping already under your belt.