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.
in reply to Re^2: Storing and retrieving a hash of objects
in thread Storing and retrieving a hash of objects
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.