Você precisará inicializar a partir de um sistema de recuperação. Como o meio de inicialização é selecionado difere entre provedores VPS.
Se você conseguir de alguma forma inicializar uma imagem ISO do Ubuntu, você pode seguir o procedimento bem conhecido para reinstalar o grub: O artigo aqui aborda muito bem: link (Você pode desconsiderar a referência para "Windows")
Se precisar de mais ajuda sobre como inicializar a imagem ISO, forneça mais informações sobre o seu VPS (talvez o nome do seu provedor ou uma dica sobre como você gerencia a máquina, a interface web ...).