I just had this same problem with exactly the same symptoms on an ASUS K56CA that I unboxed yesterday, and boy I am glad I did not come to this thread first. Lots of good advice, but none of it (would have) helped me!
Try a different USB stick. I was using a U3 16GB stick that never had problems booting on any BIOS-based computer, and I could never get it to show up reliably in the boot menu. (Once it appeared in F9 menu, only after I had removed it during boot.)
I switched to a 2GB "24x" PNY Attache I had lying around, with no embedded U3 partition, and it showed up immediately when I had any EFI-supporting image copied to it. Unfortunately I still was not able to boot from the USB. (Grub would load, but no love after selecting any choice from the boot menu.)
Finally I was able to boot Ubuntu using a DVD media with the same image written to it. The helpful folks in the #ubuntu /freenode
IRC channel informed me that you do not need a special image secure-linux-12.10-anyfoo.iso
as the Ubuntu guide instructs, just use an up-to-date 12.10 amd64 image and it will have included EFI booting support.
For me, after all this, it happily showed up in either F9 or ESC menu for alternate booting.
F10
to save. Press Escape again on reboot: This time the USB bootable device should appear in the menu. ( Source: wiki.archlinux.org/index.php/ASUS_Zenbook_Prime_UX31A )