Решил сам следующим (достаточно прозаичным) способом.
Загрузился в Ubuntu Live CD, скачал и запустил Boot Repair:
sudo add-apt-repository ppa:yannubuntu/boot-repair
sudo apt-get update
sudo apt-get install -y boot-repair && (boot-repair &)
После запуска нажал "Advanced options" и установил галочку "Rewrite system efi files" или что-то вроде того. Перезагрузил - все работает.