To boot in EFI mode, an external boot medium needs to have an EFI-mode boot loader (EFI/BOOT/bootx64.efi) on a filesystem that the firmware can read. The symptoms you describe are consistent with this not being the case. Two causes are common:

• No EFI boot files — Some programs for creating bootable USB media from Ubuntu’s .iso files omit the EFI-mode boot loader entirely, or put the EFI boot loader in a non-standard location. This is true of Pen Drive Linux (aka YUMI and one or two other names), for instance. Others require that particular options be set before they’ll create EFI-bootable media. See my notes on a few programs for more details.
• Quirky incompatibilities — Sometimes a boot medium works fine on one computer but not on another. This can be because there’s something odd about the boot medium that’s fine with some computers but not with others or because of a bug in the firmware.

In both cases, the solution usually involves creating the boot medium with another tool, although sometimes adjusting options in the tool you’re using may do the trick. As you mentioned NTFS and FAT, be aware that all EFIs support FAT boot media, but I have yet to encounter one that supports NTFS. (I’ve seen a small number of posts that claim NTFS support in particular computers, but I have yet to see evidence backing up these claims.) Thus, you should stick with FAT, if the tool gives you an option. (Furthermore, FAT32 is more reliable on some older computers than is FAT16 or FAT12, so using FAT32 may be helpful.)

Based on my own experience and online reports, Rufus is one of the more reliable and flexible tools for this task, but the last I checked it was Windows-only. In Ubuntu, dd seems to be pretty reliable, although some computers dislike the Frankenstein’s Monster format that a dd copy of the .iso file to a USB flash drive creates, so in some cases you may need to use something else.