Today I tried to apply the Dynamics 365 update to a couple of CRM organisations that were running on v8.0.1.79. This failed and in the log file I found the following error:

dbo.SolutionBase' with unique index 'ndx_UniqueName'. The duplicate key value is (SnapshotSolution80)

Just to explain what I believe has happened here, I think that someone at Microsoft created a solution snapshot in V8.0.1.79 with the unique name SnapshotSolution80. This Snapshot Solution is removed from the DB when you apply update V8.1.0.359.
Later, in V8.2.0.749 the same unique name is used on a different solution snapshot and when the CRM tries to insert this record into SQL it throws the error mentioned above because you never applied update V8.0.1.359 to remove the duplicate key.

How to fix it

1 Restore DB to a CRM server running CRM V8.1.0.359

2 Attempt to apply Update to CRM DB. If it fails with the error:

Cannot insert duplicate key row in object 'dbo.SolutionBase' with unique index 'ndx_UniqueName'. The duplicate key value is (SnapshotSolution80)

Delete the Stored Procedure [dbo].[p_RetrieveMultipleDirectAncestors] (Don't worry, the update puts it back. ) and try to apply update to CRM DB again.

3 After the update succeeds, backup the DB and move it back to the CRM server with CRM V8.2.0.749. This should apply the update.

Sources: Note Shrikant Karpur's answer. This worked for me and is far less destructive than all of the other answers in that thread. Note this isn't actually the correct solution to the issue he mentions, but it did lead me down the right path so it bears mentioning. Please do not change any unique names of any solutions. You could break something important.