It looks like in your use of Storeable, you are not just storing a hash, but are storing a hash whose values are objects of a class. Storable won't know how to serialize and de-serialize those objects unless it can find that out from the class. The first thing to check is whether Set::IntervalTree provides the methods that Storable needs. I'm guessing that it doesn't.
The documentation to Storable tells you about the methods it needs in the Wizards Only --> Hooks section of the docs.
Hope that gets you the basics of what you need to decide how deep you want to get. Someone else may have a recommendation on how they have serialized Set::IntervalTree objects. --Rodion