Boas,
Existem diversas variantes a ter em conta. O principal não é a distancia, mas sim a empresa e a qualidade dos servidores,serviços,etc...
Em primeiro lugar, na sua atual empresa, o problema não estará no seu site? Por exemplo, no caso de ser um site wordpress, não estará com algum problema de configuração ou erros?
Qual é exactamente a explicação que a empresa apresenta?
Se estivermos a falar de quedas constantes consistentes com inacessibilidade do servidor, então isso é diferente (e nesse caso, deve mudar). Quando voltar a verificar problemas no seu site, como a inacessibilidade, teste carregar o seu site e o IP do servidor via o Pingdom Tools - http://tools.pingdom.com/fpt/
Poderá tambem testar o ping e/ou outros websites de clientes da empresa.
Em resultado:
Se apenas o seu site estiver offline (e não o IP/pagina do servidor/outros sites no servidor) - Então, muito possivelmente, será algo relativo ao seu site.
Se ambos estiverem inacessíveis - Será algo efectivamente do servidor.
Se ambos estiverem acessíveis - Então será um problema diferente relacionado com a sua ligação ou com algum bloqueio do seu IP.
Em todo o caso, quando à sua questão, é sempre recomendado utilizar servidores próximos da localização da maioria dos visitantes. No entanto, ao longo dos anos, esse desfasamento é cada vez menos importante.
Alias, pode facilmente solucionar esse problema ao ativar um serviço como o Cloudflare, que distribui o seu site e conteúdos por vários servidores a nível mundial.
Agora, deve tambem ter em conta a empresa para onde irá mudar. Não será "mais do mesmo" ou ainda pior?
Procure alguns feedbacks online sobre o nome da mesma.
Note que empresas como a Hostgator, JustHost e afins podem parecer ter boas reputações, mas, na realidade, quando ocorre um problema o suporte deixa muito a desejar e existem vários outros problemas (como limitações elevadas). São milhares de clientes e, por vezes, pode demorar várias horas ou mesmo um dia inteiro para obter uma resposta a um simples email...
Resumindo: antes de tudo, pesquise bem a empresa.