This problem occurs as Magento is not very good at clearing out shipping methods when you delete them.  The shipping method can be the name of any shipping extension you have deleted.

Suggest you backup your database first, especially if you are not comfortable around sql.

To resolve go into phpmyadmin, get up a SQL prompt and do the following:

select * from core_config_data WHERE path like "carriers/matrixrate%";

If you are happy that the result set is that which you want to delete (should be around 15 rows) do following:

If you get invalid SQL syntax can you replace the quotes above with quotes " from your keyboard – it gets confused in the copy/paste translation sometimes.

Replace ‘matrixrate’ with your shipping carrier name in above SQL.