Summary:

A territory is unable to be deleted even if the users assigned to it have been deleted.

Symptoms:

If you try to delete a territory that had users assigned to it before they were deleted you will get a SQL error.

Workaround:

Change the users territory to one that will not be deleted (worldwide) before the user is deleted. This removes the link to the new territory that was created.

More information:

This has been addressed and fixed in 7.2f which is due for release at the end of September 2014.