Ok... I'm not sure what here applies to Mozambique, but I discovered three related issues. They were:

1. Some countries were using the wrong country ID for the address format, most likely just a copy mistake and usually from Austria. I fixed these.
2. Some countries were using a leading 0 that was screwing up PHP's intval() or something so that it evaluated to 32 instead of the real ID. In any event, I took out the leading 0's.
3. The uc_set_address_format() function was getting a validated country ID and then not using it. Fixed that.

These changes will be committed shortly.

(Oh, I also got tired of scrolling down when importing new countries, so I moved the import form above the table and updated the help text. )