Please check in the admin panel that you have set the 'Sender address for all administrative messages' to something sensible. This is used as the 'From' address on outgoing emails - if it's not valid, some web hosts might not allow the emails to be sent out.