The issue is that they had to change the whole character and game database structure and related processes in order for Warbands to function. Character data may seem simple, but when it now impacts the whole Battlenet account in a huge way, and every other char on it, that is not insignificant.
The tools for players to restore deleted chars into the new database structure are not done yet. They took the restore function offline before Warbands for that reason, I assume.
If anyone got an exception I would guess it was escalated to a specialist who manually handled the data restoration into the new data structures.
The tool will return when they have it set up to properly put the character data back into the new system.
I don’t work there so I could be wrong, of course, but I THINK that is what is going on.
Here is a thread talking about Datacenter Maint that was major down time back at the end of June. Just before the patch that implemented Warbands. Discussion in the thread is about the Database and about the Datacenter.
So it is not unreasonable to put massive database changes and datacenter upgrades together with Warbands coming out and conclude that Warbands and other functions they released required those changes.