Grub warning- xen
A bit late, I know, but I just had a similar issue and solved it by renaming /etc/default/grub.d/xen.cfg to /etc/default/grub.d/xen.cfg_bak, so grub does not find it and then just removes it from the menu .
Apparently Xen does not remove the grub configurations upon uninstallation, so just hiding them and then updating my grub (via update-grub on Ubuntu 15.10) was enough to fix the issue.