Sé que ha pasado un tiempo desde que se hizo esta pregunta, pero estaba teniendo problemas similares (aunque con 14.04) y pensé en publicar mi solución.
También tenía instalado QGIS 1.8 (y luego intenté esto con 2.18 sin éxito), y la solución dada por jbalk no funcionó porque esta opción no existía en la lista desplegable. Si bien el controlador OpenGDB está instalado en QGIS de forma predeterminada, solo es el caso cuando se compila con GDAL versión 1.11.0 o superior (consulte el comentario de RyanDalton sobre la compatibilidad con la geodatabase de archivos (*.gdb) en QGIS?). Al instalar la versión estable de QGIS según las instrucciones del sitio web de QGIS, terminé con una versión GDAL de 0.9.#.
Puede comprobar su versión de GDAL escribiendo
gdalinfo --versión
La forma más fácil de arreglar esto ahora (quizás esta actualización no existía en 2013) es instalar usando los repositorios basados en ubuntugis de acuerdo con las instrucciones en el sitio web de QGIS. La versión de GDAL se actualizará (la mía actualmente es 2.1.0), el controlador OpenGDB funcionará de inmediato y podrá seguir las instrucciones de jbalk.