Hmm... I think this is more a user interface problem than a bug. I tested this on a test site, and I believe the problem arises when you remove countries from the site without first setting the store country to a newly installed one. It's fairly lame, but the solution is to go adjust your store settings at admin/store/settings/store/edit and resubmit that form. Then it'll be fine on the checkout page.

You're totally right about this. Thanks.

We should put this in the docs somewhere ... i am not allowed to edit documentation :-/ See my next issue