Hi Till,
thanks for your hints! That was driving me crazy (and more then once I cursed the Debian team for moving to insserv

)
After all the mess, the solution was quite simple. The fuse module was indeed responsible for the glusterfs problem and the glusterfs problem stopped the apache from booting.
Here is what I did to fix the problems, just in case anybody encounters the same problem:
cd /etc/insserv/overrides/
cp ../../init.d/fuse .
nano fuse
in the LSB header remove the two references to $remote_fs
Code:
#! /bin/sh
### BEGIN INIT INFO
# Provides: fuse
# Required-Start:
# Required-Stop:
# Default-Start: S
# Default-Stop: 0 6
# Short-Description: Filesystem in userspace
# Description: This file load all what's needed to make fuse work fine
### END INIT INFO
insserv -n fuse
insserv fuse
Note: This removes the ability for fuse to mount nfs shares during boot (because we removed the remote filesystems dependency from fuse and the network shares are loaded later), but since I use fuse for glusterfs only, that was not a problem. If you need fuse to access nfs shares at boot, you cannot use the above fix!