Workflow Failing after Final (HR) Approver and Displays US Home Address error on Transaction Console

Summary

Workflow Failing error: Employees assigned to a payroll must have a US home address

Content

Since moving to the new UI we have had some intermittent failures of promotion workflow with the error "Employees assigned to a payroll must have a US home address."  We have opened an SR.  This only happens on some promotions and because it is a promotion, the employee already has an address record in the employment record. What thing in promotion record would cause this? Since this is failing after the final approver, it seems less a part of workflow and more a part of the act of trying to write/commit the record to the database.