Emails from Contact form and Newsletter Signups not being sent

All the emails related to registration are being sent just fine. email to the new user and the admin are both sent as is any lost password email. The newsletter optin in the footer accepts the email address and adds them into the newsletter section of the admin panel but no email is ever sent to them to confirm. In addition, the newsletter optin widget in the sidebar gives an error when someone enters the email and clicks join, See the attached image.

I imported an email into the newsletter list and then sent out a newsletter. The email was received by the imported email but not by the email that joined via the footer optin ( because it was never verified as it didnt receive that email )