I managed to find the solution not long after posting the question. For anyone else:
The problem was that I was trying to assign the DataGridViewComboBoxCell.Value to an object, expecting that because the Cell was bound to a data source that it would automatically find the object in the source and update.
This wasn’t actually the case, you actually need to set the value equal to that of the ValueMember property for it to correctly update the value and binding. I believe I was using a property ‘Name’ for both ValueMember and DisplayMember (controls how the renders in the cell) so setting the Value to interface.ToString() (rather than the interface instance) works for the majority of cases. Then I catch and ignore any DataError exceptions that occur while I’m changing the source around.