Comment 53 for bug 138691

Well, one thing I found very valuable when debugging my version of this problem (apparently, there are several causes resulting in the same or at least very similar behaviour) is this:
In /etc/default/rcS, make sure that "VERBOSE" is set to "yes" (default is no). That way, some of the scripts in /etc/init.d will be, well. more verbose - only after making this change did I doscover that the shutdown did *not* hang at "Sending...KILL... processes" (which comes from /etc/init.d/sendsignals), but rather later in /etc/init.d/unmountnfs.sh. Unfortunately, there are several scripts running after 'sendsignals' that do not print any output to the screen, unless VERBOSE is yes. In the end, I even added 'echo' statements to some scripts in /etc/init.d just to find out where *exactly* the shutdown hung.

I would like to suggest that everybody who experiences this kind of problem tries to look into this - the more precise we can pinpoint the exact location where the shutdown process hangs, the greater the chance that the developers can actually solve this.

To the developers: I forgot to mention that - just before removing NetworkManger - I also found a way to get rid of its error messages at shutdown without removing it.I copied "K20dbus" from /etc/rc1.d to /etc/rc0.d, figuring that if dbus needed shutdown for single user, it would also need shutdown for shutdown... After that modification, NetworkManager did no longer spew that bunch of warnings and error messages that the original poster described. It did, however, not solve the problem with the hang.
Of course, I'm used to a fully blown Sys V compatible runlevel mechanism (as used e.g. by Red Hat, SuSE, Mandrake) rather than what (K)ubuntu does, so I might well have overlooked something here.