I got off the phone with Delta's web support. We noticed that I had an French-based address in my profile as well as a couple French-based credit cards. We erased all that and the rep told me that it should fix the check in problem. Of course I don't have an international flight immediately planned so I don't know if that's true.

It would be interesting to know, among people who responded to this thread, if the ones having the problem have international addresses listed and the ones who don't have the issue don't have international addresses listed.