Sem ver os registros reais, você desejará fazer um DIG (ou NSLOOKUP) no domínio e procurar o que é retornado com e sem o www.
É assim que o stackoverflow.com está configurado. Se estiver faltando um registro CNAME ou A para o www e o sem, esse é o seu problema.
stackoverflow.com. 1200 IN A 64.34.119.12
www.stackoverflow.com. 1200 IN CNAME stackoverflow.com.
Se você postar o domínio, poderemos ajudar melhor. Além disso, esta questão deve estar em serverfault.com, eu solicitei que ela seja movida para lá, pois não está relacionado à programação.
EDIT: 10/10
Já que você está vendo o registro A, mas a internet não está, é possivelmente devido ao domínio apontando para os servidores de nomes errados.
Name servers:
dns1.fluent.ltd.uk 195.78.94.253
dns2.fluent.ltd.uk 195.78.94.254
Você mencionou a troca de hosts da Web, se esse não for seu host atual, será necessário entrar em contato com 1 & 1 AG e peça-lhes que alterem os servidores de nomes para o seu host atual, para que a Internet veja os registros DNS corretos.