A territory is unable to be deleted even if the users assigned to it have been deleted.
If you try to delete a territory that had users assigned to it before they were deleted you will get a SQL error.
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.
This has been addressed and fixed in 7.2f which is due for release at the end of September 2014.