I think I had the same problem. The problem may be how your mail clients are setup.
And it depends if PHP is configured to use the PHP mail function or the SMTP mail client.
Anyway, what I did was to install “WP-Mail-SMTP” -plugin and configured my email account details to use SMPT, then it worked perfectly fine. I have windows Vista so I think this may be a difference between Linux and windows.
