Redirecting domain name = dead email?

Well yes there is a waiting period for your domains & mx records to propagate, but you do have to set up the email accounts with your new web host manually, they don't just update themselves.

I recently switched my web host and I did all my email addresses at the same time as my domains, but the email setting did have to be set up in a different section of my admin panel then my domains.

Who is your new host? Log into their admin panel and look around for email accounts.