Comment 5 for bug 1633839

That made me think about grub, so i reinstalled grub as described here https://help.ubuntu.com/community/Grub2/Installing#Reinstalling_GRUB_2_from_a_Working_System

sudo grub-install /dev/sdX
sudo update-grub
sudo reboot

and voila, the error message is gone.