Can you send any type of mail? The test mail? The confirmations of orders? From another program on the same server?
If not it might be time to check for errors in the mail system in general (not Prestashop). If it is you own server you might look at mail.log in the /var/log directory. If you have a hosting provider you might ask them to check things.