Make sure you don't run in single-user mode. Fire up a terminal, as root, then issue the command
and hit enter
You're now for sure booting in runlevel 2, that has networking enabled by default
(I know Red Hat defines different runlevels, each with their own bootscripts, but in Debian, runlevels 2-5 are all equal. How democratic is that
) If that doesn't make a difference, try re-installing the network manager and see if the problem vanishes that way. If it does, find out what packages the network manager depends on, then mark those as keepers when you remove it again.