Ian - It appears that the individual packages that are generating these messages are misusing the functions in /lib/lsb/init-functions; the newlines are being produced by those scripts, not by the functions themselves (which, if used properly, will give output indistinguishable from the "old" logging style unless the init functions are overridden).
Incidentally, the functions Debian packages should be using are not the ones mandated by the LSB; instead, they are designed to allow either Ubuntu-style or policy-compliant logging (or some other logging design) with the same calls, so changes to init scripts are no longer necessary. My advice - figure out which packages are making ugly log entries, and file bugs accordingly, directing the maintainer(s) to read /usr/share/doc/lsb-base/README.Debian in its entirety. Chris
