Maybe try the holding down send/end and the power button while hitting the reset to do a hard reset that way? I would think that would be the sure fire way to make sure its gone!
(althought I would think the cert would have been wiped with just the clear storage...)