Well, I'd seen AppArmour come up as top result in google a couple of times, but had ignored it because I was foolishly sure that auditd was generating them. Eventually I searched for "ubuntu 9 dmesg audit" and the second result was
this.
And yes, it seems to be udev. There's a
bug report, which is mentioned to affect Lucid/Maverick/Natty. No mention is made of Jaunty/Karmic, but there doesn't seem to be any consensus on what's actually going wrong...
A similar problem is described
here, which is solved, but there the pause is
after the udev message rather than before. Still, no harm in trying
Couple of other suggestions; you're running version 9, which is no longer supported. Have you considered upgrading to at least Maverick? It wouldn't need to replace your current install, you could do it side-by-side until you've checked whether the problem persists. It's probably a good idea anyway, as you're missing out on potentially important updates. If
that fails, and the problem is big enough to bother you, I would humbly suggest trying another distro. I eventually got annoyed enough at Ubuntu's speed issues that (after a couple of false starts) I settled on Arch as a nice, relatively easy to use, configurable and fast distribution. Obviously, it's down to personal taste
Best of luck,