Então, de fato, descobriu-se que o problema tinha a ver com compilações paralelas e, em particular, no final, quando o módulo python estava sendo religado, outras coisas ainda não haviam sido resolvidas. A correção também foi, na verdade, menos uma correção e mais uma solução e é exatamente o que eu propus.
Ou seja, simplesmente adicionei esse destino ao meu arquivo debian/rules
:
#because python module depends on main library and somehow dependency is not known we must limit parallelism
override_dh_auto_install:
dh_auto_install --max-parallel=1
O --max-parallel=1
bit limitará a execução de make -j1 install
, o que evitará a condição de corrida em que a libtool está procurando uma biblioteca que ainda não esteja lá (descrita no link acima) ao reconectar o módulo python.