A entrada na Lista Negra será para o IP do servidor, não o domínio. Qualquer domínio que envia email desse servidor pode ter problemas ao fazer isso. Não deve haver nenhum link entre o seu IP sendo colocado na lista negra e o seu domínio.
Isto supõe que você não foi a causa do IP ser colocado na lista negra. Se você estava enviando spam de seu domínio, talvez seu domínio também tenha sido colocado na lista negra.
Se esse não for o caso, é provável que os dois problemas não estejam relacionados. Pode haver problemas mais gerais com seu e-mail. Você tem configuração de DNS reverso adequada? Um grande número de grandes provedores de correio analisa isso ao decidir entregar e-mails. Você está recebendo qualquer retorno por correio não entregue. Eu diria que olhe para seus logs do servidor de email, mas obviamente isso não é possível com o Gmail. Se você está pagando pelo Google Apps for Domains, eu levo a questão para o Google.