The Labs Team confirmed that this is caused by a bug in Package andamp Deployment. A new bug item was logged for the Developers to investigate fully and fix in a future version of K2.
The following Workaround was provided:
In the Source Environment on the affected Workflow Event, remove any configured Data Bindings
Create a Package
Deploy the Package to the Target Environment
In the Target Environment on the Workflow Event, re-add the Data Bindings and Deploy the Workflow using K2 Designer.
The client tested this on the affected Workflow and confirmed that the workaround was successful.