Файлы библиотеки обычно находятся в /usr/include/qt4. Qmake находится в /usr/bin/qmake-qt4 (или /usr/bin/qt4-qmake, я забыл). Возможно, вам понадобится символическая ссылка /usr/bin/qmake на любой из них.
Возможно, ваше приложение ожидало, что файлы будут находиться в /usr/local/include... и /usr/local/bin..., как и в некоторых других вариантах?
В конце я понял, что на обеих машинах установлены разные версии gcc (g ++). Я строил с 4.8 и работал там, где было доступно только 4.7. Установка 4.8 на целевом компьютере (как описано здесь) решила проблему.
Может быть более легкое решение, которое не требует установки полного компилятора, а просто требуемой библиотеки.