So, i have had a look at the settings and they all seem to be fine.
This is what i have for my emails etc:-

E-Mail Transport Method ---- SMTPAUTH
Send E-Mails (This one should be 'True')n ---- TRUE
SMTP Email Account Mailbox (don't publish this here, just check it is correct) ---- CORRECT
SMTP Email Account Password (don't publish this here, just check it is correct) ---- CORRECT
SMTP Email Mail Host ----- gator4142.hostgator.com
SMTP Email Mail Server Port ---- 465

And those too, generally set to same values as above:

Newsletter SMTP Email Account Mailbox (don't publish this here, just check it is correct) ---- CORRECT
Newsletter SMTP Email Account Password (don't publish this here, just check it is correct) ---- CORRECT
Newsletter SMTP Email Mail Host ---- gator4142.hostgator.com
Newsletter SMTP Email Mail Server Port ---- 465


Now, the weird thing is that i have found out that I can receive emails but not send them.
This is not a Zen Cart issue but an issue with my host - Hostgator.

I need to get them to fix the issue on their side and then i can test the newsletter feature again.

Will keep you all updated - thank you