1- Você, já tentou ver se não corrompeu a instalação do hd externo? ele ainda funciona nas máquinas que funcionavam antes?
2- Algumas placas, senão todas hoje em dia, tem uma opção de apertar uma tecla de função F12, F11, F8, algo parecido durante a inicialização para escolher a mídia de boot, ignorando as configurações do setup, veja se não funciona ai.
3- Verifica a ordem dos dispositivos usb no setup, tive alguns problemas com isso, colocava o boot por usb primeiro, mas o dispositivo que vinha na frente era outro, inclusive tenho um note sem hd com lubuntu mini instalado num pendrive, se plugo ele em outra porta usb não funciona.
4- Por último, encontrei um problema semelhante ao testar o ubuntu 13.04 beta na maquina virtual, pensei que a imagem estava corrompida, baixei outras vezes e nada, alterei alguma configuração na máquina relativa as unidades de armazenamento, algo que era bem simples mas não me lembro o que foi, e funcionou.
Então procure nas configurações do dispositivo usb no setup também (cuidado, antes de alterar anote o valor que estava)
Se eu lembrar o que foi que alterei na máquina virtual para funcionar eu retorno aqui.