chrooting into a livecd image and running a nonexistant command gives:

[root@synephrine /]# nm
Command not found. 
** ERROR **: This program cannot start until you start the dbus system service.
aborting...
Trace/breakpoint trap

This is a bit misleading, since starting dbus isn't going to make nm suddenly start working.  It also doesn't match the normal bash not-found message, but meh.

Cheesy workaround is to hack the alias like so:

command_not_found_handle () {
    [ -S /var/run/dbus/system_bus_socket ] && /usr/libexec/pk-command-not-found $1 || (echo "bash: $1: command not found" ; return 127; )
}

but then you have to repeat that for tcsh and so on.  Better would be to have pk-c-n-f do the check itself.