Une autre piste :
Essaye d'ajouter dans /etc/default/grub une ligne concernant GFXMODE, chez moi j'ai GFXMODE=1280x800.
Je dis ça car dans /etc/grub.d/00_header il y a :
if [ "x${GRUB_GFXMODE}" = "x" ] ; then GRUB_GFXMODE=auto ; fi
Ce qui semblerai signifié qui si le GFXMODE n'est pas défini, grub cherche automatiquement la bonne résolution, et c'est peut-être ça qui prend un peu de temps (mais je peux aussi me tromper...)
Pour savoir quel sont les résolutions supportées par ta machine, dans l'écran de grub tu appuie sur la touche « c », tu aura une invite de commande, et tu fais vbeinfo, ce qui te donnera les résolutions possibles.
Ensuite tu ajoutes cette résolution dans /etc/default/grub , par exemple GFXMODE=1280x800 et ensuite un petit coup de
su -c 'grub2-mkconfig -o /boot/grub2/grub.cfg'
pour que cela soit pris en compte et tu redémarres.
Mais je ne suis pas du tout sur que cela résoudra ton soucis, mais cela n'empêchera pas le démarrage...