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:
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
Replace 'matrixrate' with your shipping carrier name in above SQL.