For your subscribers, suggest that they add the newsletter email address to their contacts list.
Secondly, run your newsletter through an email testing service like
Litmus to test it against common spam filters. That way, you can begin to eliminate possible causes of your messages being labeled as spam.