Do you have error messages in the mail server logs?
Did you follow this guide?: Email Troubleshooting