Multiple Table Rates (aka multipletablerates) was a very popular extension in the magento 1.3 and earlier days... However, after several magento versions this extension basically became completely unstable/buggy (this is normal as it only lists magento 1.1 compatability)... Even so, it still worked on magento 1.3 with a few minor bugs... Then later down the road other extensions came up (mostly paid) that provided similar functionality, plus some, and minus the bugs...
This is all good and all, however, uninstalling multipletablerates from magento (using magento connect) didn't properly uninstall the extension... hence you would get strange errors when using other table rates extensions (it would work 99% of the time, and then for 1% it would show an error for the estimated shipping quote.
Anyhow the solution:
You have to go into the database and delete the multipletablerates entries manually...
delete from core_resource where code = 'multipletablerates_setup';
delete from core_config_data where path like 'carriers/multipletablerates/%';
drop table shipping_multipletablerates;
Clear all magento settings cache, log out, and log back in.... and that should do it.