For EFI boot you need to form a specific structure of the image's filesystem, not just bootsector (since it's unused), so have a look at Ubuntu's live-helper scripts (my guess) or examine mki-copy-efiboot script (the part of mkimage which I wrote and use).
In case you just need a custom rescue image, not neccessarily an Ubuntu-based one, you might like my ALT Linux Rescue as the technology behind it is both open and explicitly created for easy derivatives (but is mostly documented in Russian which didn't stop some people) -- it's basically about grabbing live-builder.iso, booting it on a spare VM/host and:
git clone git://git.altlinux.org/people/mike/packages/mkimage-profiles.git
cd mkimage-profiles
make regular-rescue.iso
grep -B6 RESCUE_PACKAGES conf.d/regular.mk
It might also be helpful to read the excellent Rod's book on EFI bootloaders as well as Matthew Garrett's ISO9660/EFI quest report.
Good luck whatever route you take!
PS: grub-mkrescue is not EFI aware as of 2.00 apparently.