O pacote BeautifulSoup está nos repositórios do Ubuntu como python-beautifulsoup . Você precisa especificar que o seu pacote depende disso.
No responda você vinculado para , dê uma olhada no arquivo debian/control - há Depends: seção onde você pode especificar as dependências do pacote.