Unfortunately, it does look like the ability to restore a deleted character if you do not currently have a character on the realm is not possible on Wrath of the Lich King Classic. That is, as far as I’ve been able to find out, currently intended functionality. Sorry.