Symptoms
Realtime shipping appears to be configured properly, but is not behaving as expected (free shipping is not being enabled, rates are not displayed, etc).
Cause
If the store has previously used fixed-rate shipping methods, the state/country/zone mappings in the database can interfere with the realtime rate functionality.
Solution
Run the following statements against your database:
DELETE FROM ShippingMethodToStateMap
DELETE FROM ShippingMethodToCountryMap
DELETE FROM ShippingMethodToZoneMap
NOTE: If you are planning to go back to fixed-rate shipping in the future, back up these tables first! This will remove all of your state/country/zone restrictions from the shipping methods you set up.