It could be a Magento related problem but it can also be a problem coming from your mail server.
First, you should try to look your
exception.log, to check if nothing is written there (assuming logs are enabled)
You can also check your apache2 / Nginx / other 's log file concerning your admin, to check is there are no exceptions.
Finaly, you should have a look at your
/var/log/syslog to check if your sendmail (or exim or whatever) is not returning an error message.
Then, post it here and someone will be able to help you.