Ok, eu peguei o arquivo do seu URL (abaixo de 800KB) e tentei isso (de um terminal do Cygwin que era útil).
$ file p4
p4: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux 2.2.5, dynamically linked (uses shared libs), stripped
Mas, você espera que ele esteja vinculado estaticamente, por quê?
Atualização: só para ter certeza, por favor, confirme que você está executando um Ubuntu de 32 bits.
Se você estiver executando um sistema de 64 bits, provavelmente precisará do pacote ' ia32-libs
'.