Comment 3 for bug 1619829

I faced this too once I wanted to switch from 304 to 367 after GPU replacement.
In my case it helped to

    sudo apt-get remove --purge nvidia*

first, and only then install the update

    sudo apt-get install nvidia-367 nvidia-367-dev nvidia-opencl-icd-367

In such a way it worked without reporting an error.