Acabo de tener este mismo problema con exactamente los mismos síntomas en un ASUS K56CA que desempacé ayer, y chico me alegro de no haber llegado a este hilo primero. Muchos buenos consejos, pero ninguno de ellos me habría ayudado!
Prueba una memoria USB diferente. Estaba usando una memoria U3 de 16 GB que nunca tuvo problemas para arrancar en ningún ordenador con BIOS, y nunca pude conseguir que apareciera de forma fiable en el menú de arranque. (Una vez que apareció en el menú F9, sólo después de que lo había quitado durante el arranque.)
Cambié a un PNY Attache de 2GB “24x” que tenía por ahí, sin partición U3 incrustada, y apareció inmediatamente cuando tuve cualquier imagen de soporte EFI copiada en él. Desafortunadamente, todavía no podía arrancar desde el USB. (Grub se cargaba, pero no se amaba después de seleccionar cualquier opción del menú de arranque.)
Finalmente pude arrancar Ubuntu usando un DVD con la misma imagen escrita en él. La gente útil del canal de IRC #ubuntu /freenode me informó que no se necesita una imagen especial secure-linux-12.10-anyfoo.iso como la guía de Ubuntu instruye, sólo usa una imagen 12.10 amd64 actualizada y habrá incluido soporte de arranque EFI.
Para mí, después de todo esto, apareció felizmente en el menú F9 o ESC para un arranque alternativo.