Do not attempt to update values in PK columns.
It's not what happens behind the scene anyway.

Here is the course of actions you need to take:
1. Create #PKmap table and populate it with CurrentPKcol and NewPKcol values.
2. Begin transaction
3. Insert into the "main" table new record(s) with NewPKcol values and the "tail" from the records where CurrentPKcol = Table.PKcol
3. Insert into all "dependent" tables new records which reference NewPKcol and contain the same data as records referencing CurrentPKcol. Table #PKmap will make it easy.
4. Delete from "dependent" tables all records referencing CurrentPKcol.
5. Delete from "main" table the record(s) referencing CurrentPKcol.
6. If you still have not an error on any of the steps - COMMIT transaction, otherwise - ROLLBACK and investigate.

You may wish to make it into a SP which would check for existence of #PKmap and do all these steps if it's not empty.