My Characters are gone!

Last time I logged in to my account and my 3 characters on Icecrown were gone, a paladin level 74 and a Warlock level 76. I changed my password and sent an email to [email protected]. But the answer I got wasn't very satisfying:
I have looked over your account and found only one character deleted.
I have restored this character.

The thing is, not even one of the characters shows up in character selection.
I really don't want to start all over again after I put like 40-60 hours into leveling those 2 characters. I don't really mind about the third Char, which was a Deathknight, but the loss of the other 2 hurts.

Is there still any way to restore them?