O Ubuntu 11.04 (Natty) suporta a inicialização da UEFI, conforme explicado por este wiki da comunidade Ubuntu .
"A partir do Ubuntu 11.04 (apenas x86_64), o CD ISO suporta a inicialização via UEFI e o instalador do Ubuntu tentará configurar o bootloader com inicialização (E) EFI."
Se você está inicializando com o Windows, verifique se está usando o Windows Vista (SP1 + 64 bits) como mínimo.