Problem is that you loose all the terms already created.
Another point no very clean: the Term Content Type created for the old taxonomy name, is no deleted, but you can do nothing with it because you loose the access to the old taxonomy record, this one has been deleted.
To clean the only solution is in editing the DB.

There should be a minimal warning when you update the name of a taxonmy saying that you will loose all its terms.

To reproduce:
1) Create a taxonomy named 'Product Types'
2) Add several terms : server, database, web site
3) edit the taxonomy and change its name to Category
-> you have lost all your terms .....
and no error in the log file...

but digging in the DB it appears that some work has been done to keep the terms under the new 'Category Term' content type created.

It seems that the missing element is that in the 2 tables :
Orchard_Framework_ContentItemRecord
Orchard_Framework_ContentItemVersionRecord
the corresponding records are not created (or updated ?) correctly.
So all the terms are still in the DB but part of their records point either to the new ContentType, part to the old one.

This could be recovered mainly by updating the last version of each term in Orchard_Framework_ContentItemVersionRecord to set Published, and Latest Columns to true then changing the ContentItemRecord_id to the new one.

On the philosophy of keeping the old records and recreating new ones, this has certainly been created because taxonomies could be sparsed through all the system, as un easy turn around for a global modification.
But in this situation the old taxonomy name should not disappear.
On my own, I would prefer to have everything migrated to the new name, keeping the history is a job for hercule. So updating rather then recreating would be preferable.
Problem seems to be in the fact that it is impossible to rename a content type in Orchard ?

A temporary action to prevent this database corruption would be avoiding any rename when some terms exist.
The best action is to correctly finalize the job and move or recreate terms under the new Term Content Type, which necessitate a better understanding of NHibernate than I actually have.