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.