This indeed still happens with xen-utils-4.1 4.1.4-3+deb7u1 Additionally, the problem is hard to figure out (as it simply excepts with "RuntimeError: Unable to find partition containing kernel", which it does in many other cases as well; perhaps it should collect other caught exceptions for debug purposes).
The grub.cfg, in my case, was generated by update-grub (from inside the guest) and contained several lines `set root="(/dev/xvda1)"` (partially because I am using a file as a guest's `xvda1` partition without `xvda` drive); which also implies that if update-grub is re-run inside the guest (e.g. on automatic update) it will break again.
