Hi,
Recently upgraded from 1.3.2 - 1.3.7.1 & encountered a few problems. Here's how I fixed them - might be useful, but equally might be specific to this one instance.

1) Zone rates - I was getting the "Zone Rates (The shipping rate cannot be determined at this time)" error on checkout. When looking at the Zone Rates module, I noticed the "Calculation Method" label was missing. So, I took a print out of the existing Zone Rate settings, then uninstalled Zones Rates, then reinstalled it & added the old settings back in. This fixed it.

I can't remember reading in the upgrade instructions about reinstalling Zone Rates (but that's not to say that it's not there in big, bold font!)

2) Paypal - payment was going thro' but no order was being recorded. I fixed this by applying the latest paypal patch. Altho' I thought'd I'd already done it, it seems something hadn't gone through correctly. So, reapplied the patch & everything worked correctly.

I've found that as this particular shop allows payment by money order/cheque (as well as paypal), running test orders using this payment method is a good barometer of problems at the paypal end of things.

Hope these 2 little tales of woe prove helpful.

Eddie