Acho que o melhor é entrar em contato com o host. Eu tive um problema semelhante na Locaweb e resolvi fazendo o seguinte:
Instalei o plugin wp-smtp (ou alguma coisa assim);
Cadastrei como email de administrador um endereço no mesmo domínio do site;
Alguns servidores desativam os scripts de sockets ou por economia ou por segurança (não querem que use o socket para flood ou spam etc). Você pode tentar contatar o serviço e pedir para ativarem esse recurso.
O jeito é tentar usar um servidor externo (SMTP), por exemplo, do gmail, do domínio etc.
http://sudarmuthu.com/blog/how-to-send-email-in-wordpress-using-gmails-smtp-server
WordPress não envia email, notifica comentários etc
Se seu servidor é pago, veja se informou um email válido em Configurações > Geral.
Se seu servidor é gratuito ou muito limitado, talvez eles não permitam usar SMTP. Verifique se há um arquivo wp-includes/class-smtp.php, se não exisitir, tente enviá-lo e faça algum teste de envio. Acontece de servidores sequer deixar o arquivo exisitir.
Estes plugins ajudam a configurar um servidor de envio SMTP externo ou enviar email, como do Gmail, mas note que se seu servidor não permitir SMTP, nenhum tipo de plugin para contato, envio de emails, funcionará.
Contate seu serviço de hospedagem para saber sobre essas limitação.
