If the emails are actually leaving your servers successfully (check your logs to make sure no obvious error is happening), then yes, you've got a spam-false-positive problem.
The solution is to make your email look less spammy, to use proper email signing (domain keys, spf, dkim, etc.) and to make sure your reverse DNS is set. This tool will find some of the more obvious problems for your.
Or just outsource the whole email sending business to a company that does this for a living: