I did some testing and found that this error was produced when the Country Code field was set. Microsoft Dynamics GP 10 didn’t exhibit this behaviour, but there is a difference in the installation of version 10 and 2010. And that difference is the VAT Daybook.
In Microsoft Dynamics GP 2010, and later, the VAT Daybook module needs to be installed to use the VAT 100 report which I had installed during the upgrade process.
In this case, the client operates only in the UK and doesn’t need to have Tax Registrations recorded in GP, so they were able to just stop setting the Country Code field on the addresses.