I had the same problem on v. 1.5.2, and it was driving me crazy as all of the carriers were configured properly with price ranges, weight ranges, and fees for all zones.
If I was not logged in, then the carriers/shipping options would display correctly for my shop's default location (United States). Once I logged in (with an address configured in the US), I would get the dreaded "There are no carriers available that deliver to this address..." mesages.
I ended up putting debug statements in the code in classes/Carrier.php and discovered that the code was calculating that I was in the disabled "North America" zone, even though it was disabled and I had created a new zone called "United States" and configured the country of United States to be in the new zone with the same name!
I then deleted all of the preconfigured zones that came with Prestashop, which had previously been disabled. Upon doing that, shipping is now working correctly.
I hope this information helps somebody.