You need to add this flag to your
.ycm_extra_conf.py file:
-isystem /usr/lib/llvm-3.8/lib/clang/3.8.0/include
I found the path by using the command line:
This command prints at the end a list of system paths automatically included by the clang binary. The Vim command
:YcmDiags also helped.
Note that this issue does not happen when building YCM from source.