So a quick search shows a lot of people are running into this issue, and have either given up, bricked their board, RMA'd it, or tried to work around it:
After trying to get EFI boot working on a D2500HN working, I ran into the same thing. And just as with other users, updating the BIOS to the latest version didn't work, doing the recovery BIOS steps didn't work, and clearing BIOS settings via the jumper did not work.
I couldn't get EFI boot to work, and as with others, legacy boot no longer worked. It appears that the Intel ATOM EFI BIOSes suffer from a bug somewhat similar to other vendors (including Samsung). Information about UEFI nvram, variable writes, and garbage collection is somewhat scattered, but there's a discussion here that should give a good idea:
To fix the issue, I got a UEFI bootable livecd of Fedora 19 (since it supports efivarfs), booted, mounted efivarfs, and was able to delete the efi variables and boot logs created in my EFI install attempts (using rm -f). This freed up enough space to change BIOS settings and allowed legacy boot to work again. Now that its fixed, I'm not planning on using EFI with these boards again.
I really hope that Intel can at least acknowledge this issue so that people know what's going on.
Thanks you for your feedback on this matter. I will forward this to the corresponding department for future considerations.