Your theory about method caching would have been my first guess. Your description of what happens to the method cache matches my understanding, and given that Perl supports multiple inheritance, there is no way that I know of to have correct behaviour without throwing away at least part of the method cache when you change the symbol table.

My suggestion for this case is to avoid laziness. Instead of AUTOLOAD (or in addition to it) have the abstract base class supply a function that autogenerates the simple getters and have that be called from each subclass. (Or you could do this in addition to having the AUTOLOAD.) The method cache still gets lost a ton of times, but all of the flushing happens before you start calling lots of methods, so it doesn't hurt so badly.