Removing 'Categories' from posts

Hi all,

I am having a problem removing the categories from my posts.

I have done all of the obvious such as going to Dashboard > Categories > Manage > Delete.

They have all been removed from there. However, When I go to create a new post they still appear in the widget on the right hand side.

This is causing me fatal time and money to get fixed as it is affecting my hierarchy.

Anyone know how to fix this?

Best Regards,
RichieC