A VPN provalmente não irá resolver o seu problema, já que você diz ser de Portugal e em seu país os IP's são liberados.
Você consegue se conectar em outros servidores normalmente? Se não, o problema está em sua internet e deve-se entrar em contato com sua provedora.
Caso consiga e no fenixzone não, adicione este IP abaixo aos favoritos de seu SA-MP e tente novamente.
IP: br.s1.fenixzone.tv:7777