Eu tive exatamente o mesmo problema em um Samsung s5. Parece que uma atualização alterou o nome da pasta de spam que o aplicativo de e-mail incorporado nos telefones da Samsung alterou de "Lixo" para "Indesejado".
Pelo link que o user367162 forneceu, a correção é entrar no aplicativo de e-mail no telefone e remover os endereços bloqueados do filtro.
Entre no aplicativo de e-mail
Pressione a tecla Menu
Selecione Configurações
Selecione as configurações gerais
Selecione endereços de spam
Remova todos os endereços que não deveriam estar lá. Por exemplo, se você ver * @ gmail.com, o asterisco está comandando todos os novos emails do Gmail para ir para a pasta indesejada. Em algum momento, quando você denunciou um e-mail como spam, pode ter escolhido bloquear o domínio em vez do endereço acidentalmente.