Summary of the solution to remove the question from the unanswered list ...
OP discovered a before-delete trigger on the table. This appears to be copying the deleted record to another table. Subsequent updates were then hitting duplicate record issues.
The stored procedure remains as it was, but the equivalent of
UPDATE Product SET ProductCode = 'D_' + ProductCode WHERE ProductID = @ProductID
has been moved to the trigger (actual tablename not known)