No shipping methods available to your location

Apologies for bumping this by starting a new thread - but I have to resolve this before the weekend.

Please help - I'm probably being stupid but I dont understand - please walk me through this.

I have set up two shipping zones UK and rest of world, each has two options small and large. All this seems OK. I have set up a tax zone of UK and set it as main in configuration.

When people go to check out the Uk is put in Ok as default and the correct postage is added but when there is the error message 'No shipping methods available to your location'.

This error message is stopping people checking out and the client is giving me grief!