Yo UN#1, your wrong for a change
It should fix itself in around 30 minutes, go play with a diff char for awhile. If that doesn't work, DO email blizzard. They even tell you to, so they can fix whatever the server is screwing up. I assume that Player Not Found stems from the server not being able to locate it or is unable to access it for whatever reason.
EDIT: D'oh! I forgot to mention that your character will never be destroyed by this, EVER. The only time that this was true was during that HORRIBLE time at which the Matrix was being mass abused, it would fork up the server extremely bad, causing it to do rollbacks to accounts, including reviving dead hc chars, killing hc chars, removing newly made chars, showing the pic of a still deleted char. It also removed newly made accounts, but didn't remove old ones. Even so, Blizz told people to delete the chars that had been brought back that you had deleted.
EDIT#2: D*MNIT! Forgot to add that it should only take blizz 1-2 hours to solve the problem at most.