The standard tulip distribution that comes with debian does not work on a 3D fglrx installation. The reason why is not entirely clear (it seems that the linkage to the X window system is faulty). However, recompiling the tulip source solves the problem.

Prereqs:
– an Xserver that uses the fglrx 3D driver. This can be tested with fglrxinfo.

Commands:
apt-get install fglrx-driver-dev
apt-get install libxml2-dev libqt3-mt-dev libqt3-headers libqt4-dev libqt4-core libqt4-gui libqt4-qt3support libqt4-sql qt3-assistant qt3-apps-dev
apt-get source tulip

go into the unzipped tulip source directory and configure the tree with
./configure --with-qt-includes=/usr/include/qt3
make

now everything should run fnie. To install tulip use
make install
/usr/local/bin/tulip