K3B misbehaving on startup

[MR ZenWiz]

I'm running Xubuntu 12.04 with the 3.8 kernel, and recently I've been
creating some CDs for my car with K3B.

Problem is that when K3B starts up, it frequently can't find one or
more of the installed commands it uses, like cdrecord, or the DVD
writer library, or something else.  The first time it did this I ran
apt-get to install the package, and it's already there.

WTH??

K3B has performed admirably for years until this.

Thanks.
MR