Apparently the last three releases of Ubuntu have been plagued by issues with bootlogd. In fact, it's been such an issue that boot logging is now disabled by default. I like to see what's going on under the hood during bootup, so I Google'd around and compiled the following tips to get it working again.
1) This thread contained a custom tarball of an older version of bootlogd. Grab the tarball from here. Then run the following commands (assuming it's saved in /tmp).
# unpack the source
tar xzvf bootlogd_2.86.02.tar.gz
# build the package
debuild -us -uc -b
# install the package
sudo dpkg -i bootlogd_2.86.02_*.deb
2) After that, make sure it's setup at the appropriate priority in the init system.
update-rc.d -f bootlogd remove
update-rc.d bootlogd defaults 08
3) Finally, make sure it's enabled.
echo "BOOTLOGD_ENABLE=Yes" > /etc/default/bootlogd
The custom version of bootlogd writes it's log to /var/log/bootmsg instead of /var/log/boot. One final gotcha: initially, I tried running bootlogd as root from inside of X, and I got the following message:
bootlogd: cannot find console device 136:1 in /dev
This is because it's not being run from the console and does not mean that it's broken. Do a ctrl-alt-F1, login as root, and you can test running it from there.