Downloadable product screws up shipping

If I have one downloadable product and one other product in the cart, the shipping estimator and shipping checkout get all messed up. In the estimator, no shipping options show up and in the checkout, the message "Sorry, we are not shipping to your region at this time." shows up.

If I put another nondownloadable item in the cart it seems to work fine (3 items total) and if I put another downloadable item in the cart (3 items total) the shipping estimator shows options, but the calculations are screwed up - even showing a negative shipping amount!

Any ideas?

Thanks!

Make sure that the Download is

1 NOT set as a Virtual Product

2 NOT set as a Always Free Shipping Product

What version of Zen Cart are you running?

Thanks! The problem was "Always Free Shipping Product".

Thanks for posting the Update that your Shipping was not working properly because your Downloads were set to be:
Always Free Shipping

And this will cause the calculations on Shipping to be incorrect ...