Comment 57 for bug 448095

Here is my quick fix, it just moves resolvconf directory creation earlier and disables invocation from rcS.d since the init.d script doesn't support running twice:

sudo update-rc.d resolvconf disable

sudo tee /etc/init/earlier-resolvconf.conf <<'EOF'
description "Prepare resolvconf directory"
start on (starting network-interface
          or starting network-manager
          or starting networking)
pre-start script
    invoke-rc.d resolvconf start
end script
EOF