It seems that nvme disks name their partitions /dev/nvme0n1. This confuses grub because the partition separator character for devices whose base names end in a digit in linux has been 'p' not 'n' since the dawn of time. Bug report forwarded from launchpad.net/bugs/1507505
This also will break parted, which assumes that the partition should end in 'p1' not 'n1'.