I have a Magento installation where the free shipping shows up if calculated on the Cart page, but if a user goes straight to the Checkout, the free shipping doesn’t calculate.
If a user goes back to the Cart page, it then calculates the free shipping and that follows them back to the Checkout.
