Решением оказалось вот что: На компе было 2 винта, один из них (главный/загрузочный) был с виндой, второй винт нужен был для установки Linux. При установке указывался второй винт для установки загрузчика, но тут я заметил, что второй винт маркируется как /dev/sdb, и при установке именно он указывается в качестве загрузчика, а первый винт маркируется как /dev/sda. При ошибке "Не удалось выполнить команду 'grub-install /dev/sda'. Это неисправимая ошибка" я вижу, что граб пытается залезть не в то место... подумал, что возможно в этом и кроется проблема.
Решение: Зашёл в Биос, переставил приоритет загрузки для винтов и поменял местами их в Boot, второй стал первым, первый стал вторым. Устанавливаю Linux Mint - вуаля! Всё работает... неожиданно, спрашивается зачем спрашивать в какой винт поставить загрузчик если grub это игнорирует и лезет в первый...