Make sure you have specified a from address for the email in the newsletter settings, typically it should be the same as the email address used for smtp settings otherwise if it seems to spoof a different email address the newsletter may be caught by spam filters.
Make sure you actually have verified subscribers with valid email addresses.
Hope it helps,
Joe