Derek and I tackled this problem for most of the morning.
There’s a problem when you switch servers and have certain Movable Type Plugins installed, such as MT-Blacklist or Multiblog. I’m not completely sure with Blacklist, but this is the fix with Multiblog.
Multiblog is a great plugin, but it writes some installation specific data into your MySQL/Berkley Database that ends up causing tons of problems if someone just dumps the database onto a new server.
The problem lies in the mt_plugindata table (or was it mt_plugin_data? I can’t remember) – the Multiblog plugin wrote one entry to this table.
Delete this entry, then log into MT and run Multiblog again.
Viola. No more rebuild errors complaining about a newer version of Storage.pm.
If you need any help with this issue, just drop me a comment.