Samsung’s UEFI implementation appears to be faulty. It was most likely tested with Windows only and found to work, but thorough testing with other operating systems doesn’t appear to have been a priority, or perhaps a consideration at all.
At present, the bug appears to affect following Samsung series laptops:
Long-term, we expect Samsung to release BIOS and firmware updates for the affected laptops, though how long that might take is unknown. Short-term, the workaround is for Linux to boot these Samsung models using the Compatibility Support Module (CSM), which basically bypasses the UEFI bootloader, but dual-booting via CSM appears to be a bit complex.
Update: It appears the problem stems from NVRAM corruption. Removing power, opening the laptop up, and disconnecting the CMOS battery appears like it will clear the problem, but that's a pretty serious set of steps to take for most laptops.