I know this question is old, but I'd like to document our solution for the same issue.
We previously had 10 or so tenants already set up and was seeing this error when trying to create an additional tenant. We had just finished a large migration of content from an old Alfresco server to the current server, so I suspected we might need to reindex upon seeing the error. Note that our system had SOLR disabled and was using Lucene, so I forced a full reindex by setting index.recovery.mode=FULL in alfresco-global.properties and restarted. Remember to set index.recovery.mode back to AUTO after reindexing. WARNING: Doing a full reindex on a system with a high number of documents can take a very long time. Proceed with caution.
You could probably do the same in a SOLR-enabled environment by deleting your SOLR indexes and restarting.