Eu tive o mesmo problema - Lubuntu 15.10 e Tulip não iniciam. Supondo que sua instalação Tulip padrão esteja em /usr/bin/Tulip , você pode verificar se há dependências ausentes usando ldd /usr/bin/Tulip .
Quando libbfd-2.25-system.so estiver faltando, instale o pacote binutils usando sudo apt-get install binutils . O pacote fornece libbfd-2.25.1-system.so . Depois crie um link simbólico com sudo ln -s /usr/lib/libbfd-2.25.1-system.so /usr/lib/libbfd-2.25-system.so .
Quando você marcar Tulip novamente com ldd , a dependência ausente deverá desaparecer e a Tulipa iniciará! Pelo menos isso funcionou para mim.