Configure GRUB on XEN VPS

I have a xen VPS with debian 7 x86_64 installed on it. The operating system comes with GRUB2 installed on it. The problem is that while runnnig

apt-get update
apt-get upgrade -y

GRUB says The GRUB boot loader was previously installed to a disk that is no longer present, or whose unique identifier has changed for some reason.. Then the following error occurs many times:

/usr/sbin/grub-probe: warn: disk does not exist, so falling back to partition device /dev/xvda1.

When I reboot after that the server would not (predictably) load.

My hosting provider tells me not to upgrade the software and refuses to help. I've found the tutorial on the topic. But I could not use it because my version of /usr/sbin/update-grub does not contain a piece of code I should change. It's entire contents is:

#!/bin/sh
set -e
exec grub-mkconfig -o /boot/grub/grub.cfg "$@"

Also I don't have /boot/grub/menu.lst on my machine

The following output may be useful

fdisk -l

Disk /dev/xvda1: 5368 MB, 5368709120 bytes
255 heads, 63 sectors/track, 652 cylinders, total 10485760 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00000000

Disk /dev/xvda1 doesn't contain a valid partition table

Could you please advise me what should I do to fix the issue?

Without knowing further details, it looks like the kernel and initramdisk for the VPS are stored on the host domain. So, when your VPS is started from the hypervisor, the hypervisor provides the kernel and hypervisor for the guest, and there is no need for any boot loader.

That means that the VPS itself has no boot manager installed at all.

It also means that you cannot upgrade the kernel or initramdisk yourself, the VPS provider must do that, because only they can access the hypervisor. It is also likely that they won't do that, since they use the same kernel and hypervisor for other VPS instances on that server.

So, the issue cannot be fixed.