Conforme indicado nos registros, o túnel GRE não pode ser estabelecido.
Talvez o seu ISP filtre o tráfego ip e deixe passar o udp + tcp + icmp, mas não o gre (ou seja, o recurso "vpn passthrough").
Outro problema com o GRE é que ele não combina bem com o NAT. Por exemplo, se você tiver dois clientes por trás do mesmo endereço IP nat-ed que se conecta ao mesmo servidor remoto, há chances de que apenas um deles consiga estabelecer o túnel gre com o servidor.
Por fim, se o seu vps estiver rodando no OpenVZ, por exemplo, seu kernel é compartilhado com o hipervisor, e talvez o módulo gre não esteja disponível. Tente modprobe ip_gre
then lsmod | grep gre
para verificar se o módulo gre está disponível em seu kernel.