WordPress Notifications not working on Amazon EC2

Wondering if anyone else is running into this issue. I'm fairly new to Amazon AWS, but my team and I recently built and moved all of our WordPress sites over to a new EC2 instance for scaling WordPress. I've utilized many of the WPMU plugins here to launch our own WP networks. Then I noticed a few days ago that none of my contact forms we working on any of our WP sites. I then noticed that the standard WP notifications (when creating new sites, or using the "Forgot Password" link) were not sending emails either.

I went through a few days of troubleshooting - disabling plugins, updating WordPress, even installing a fresh version of WP, even installed a completely new WP website under a new domain name. Nothing seems to fix the problem.

I have a few support emails and posts out to various sources, but I wanted to try here as well because it seems we are all more 'seasoned' WP users and know a bit more about the development/technical aspect of running WP, networks, etc. Maybe someone else is/has experienced this problem with Amazon AWS and can help?

Much thanks in advance!
Shawn