This bug was cured by installing libclang-dev, which is based on clang 3.5. I had some clang 3.4 packages already installed, and had installed libclang-3.4-dev too, but that doesn't seem to work with this vim-youcompleteme package, presumably because it was compiled with 3.5. So I think the package just needs its dependencies fixed to make sure the correct version of clang is installed at run-time.
This bug was cured by installing libclang-dev, which is based on clang 3.5. I had some clang 3.4 packages already installed, and had installed libclang-3.4-dev too, but that doesn't seem to work with this vim-youcompleteme package, presumably because it was compiled with 3.5. So I think the package just needs its dependencies fixed to make sure the correct version of clang is installed at run-time.