Rob already raised an interesting point that we should rather call programs with relative name, i.e. "kinit" instead of "/usr/bin/kinit" to avoid problems when the program is being run on other platform with different absolute path.

This is what I would propose:
1. PATH should be always set unless it is overriden in env. Now, when any env is passed, PATH is omitted:

def run(...):
    ...
    if env is None:
        # copy default env
        env = copy.deepcopy(os.environ)
        env["PATH"] = "/bin:/sbin:/usr/kerberos/bin:/usr/kerberos/sbin:/usr/bin:/usr/sbin"

1. PATH definition should be moved to platform code so that other platforms can override it, change paths precedence, whatever.
2. We change all our binary calls to relative format (unless we call binary not in standard PATH).

I would propose that we instead fix our build system to make paths to (not just) binaries customizable at build time using autotools (or whatever). That would solve more than just this particular issue and clean the whole guess-where-a-file-is mess.

If you just want to enfoce the non-absolute paths, make run check for the first parameter not to start with a slash (and fail if it does).

This was resolved with the platform code.