Make the linker point to the .so (shared object) file and not the .a (static lib) file.
You can do this specifying the flag when running cmake:
cmake -G "Unix Makefiles" -DPYTHON_LIBRARY=/usr/local/lib/libpython2.7.so . ~/.vim/bundle/YouCompleteme/cpp
Do mind that even though you're using pyenv, YouCompleteMe build may point to an undesired python build as they are not correctly auto-detected right now.
If you're having this problem, you should probably also specify the Python header files correctly:
cmake -G "Unix Makefiles" -DPYTHON_LIBRARY=/usr/local/lib/libpython2.7.so -DPYTHON_INCLUDE_DIR=/usr/local/include/python . ~/.vim/bundle/YouCompleteme/cpp
PS=(I'm assuming your headers are in that path, do check before)