Sounds like a table is out of date or lost some data ...

If you look via phpMyAdmin at the table:
address_format

how many records do you see?

If you look at the table:
orders

do you see the data in there and do the 3 fields containing:
_address_format_id

have valid numbers based on the table:
address_format

Did you run the Upgrade from the /zc_install for v1.3.9h or did you try to upgrade in some other manner?