La versión de repositorios de Eclipse para Ubuntu nunca ha funcionado perfectamente, siempre hay que ajustar algo.
En Ubuntu Lucid Lynx no vamos a encontrarnos con la excepción.
En mi caso, el error se presentó al querer instalar PhpEclipse. Durante el proceso, recibí un mensaje de error.

Ahora bien, a diferencia de otras veces, me puse a buscar (no puede ser que siempre haya problemas con ésta ide).
Después de leer muchísimos threads y hacer unas cuantas pruebas en más de un desktop, encontré que la forma para solucionarlo era agregando paquetes de Eclipse que por defecto no se instalan.
Para solucionarlo, vamos a buscar si los paquetes eclipse-pde eclipse-jdt eclipse-rcp están instalados.
root@linux:~# aptitude search eclipse-pde eclipse-jdt eclipse-rcp
p eclipse-jdt - Eclipse Java Development Tools (JDT)
p eclipse-pde - Eclipse Plug-in Development Environment (PDE)
i A eclipse-rcp - Eclipse Rich Client Platform (RCP)
En mi caso no lo estaban, así que sólo había que instalarlos.
root@linux:~# aptitude install eclipse-pde eclipse-jdt eclipse-rcp
Ahora bien, volvemos a probar la instalación del plugin y al finalizar deberían poder iniciar un proyecto php normalmente.

Problema resuelto.