Então parece que não era o ISO, afinal. Em algum momento notei que o stick USB tinha uma tabela de partição GPT nele. Assim, seguindo as instruções no link
Eu redefino por:
#livecd-iso-to-disk --format --reset-mbr --overlay-size-mb 1024 /home/alf/Fedora-Live-MATE_Compiz-x86_64-21-5.iso /dev/sd
Que me deu um pau não-uefi. Gostaria de poder dizer fácil e intuitivo - não é.