Hi Jason,
Please run the Restore-AzDeletedWebApp command with -Debug on the end of it and post the output here (hide any sensitive info first). Would like to see full error message/details.
I assume if you try to restore the web app via the portal you receive same error? Please confirm.
Thanks.