Warning - No Shipping Methods Available

First of - I have read many posts before making my own, and cannot find an answer.

I am getting this error message when using Flat Shipping Rate ONLY.
It doesn't effect every product, only a few.

I cannot identify any differences in the products config, and all testing is being done using the same account so no geo zone differences.

Is this a bug?

Thanks

New info-

I believe this may be linked to the products value. I had free shipping on items over £500, which is the products that seem to be affected. However the problem persists after uninstalling the free shipping module..



EDIT- scratch that, it isn't limited to products over £500

Did you make sure it's enabled for all Geo Zones?

I only ship within the UK so only have that geozone...

Anyone have any idea?