Similar here with Gutsy (Edubuntu). I try to setup autofs with automount maps in LDAP and NetworkManager uninstalled. My guess is that autofs gets started before slapd, can not find the maps and decides nothing to do. A simple
update-rc.d -f autofs remove
update-rc.d autofs defaults 20
For me it works.
The changelog, however, states that autofs start was lowered to level 19 instead of level 20 (somewhen in 2005) because of other daemons relying on it.