Google test was probably not properly installed (libgtest-dev may install only source files that needed to be compiled). I had the same problem and I followed the instructions from http://www.eriksmistad.no/getting-started-with-google-test-on-ubuntu/
sudo apt-get install libgtest-dev
sudo apt-get install cmake # install cmake
cd /usr/src/gtest
sudo cmake CMakeLists.txt
sudo make
#copy or symlink libgtest.a and libgtest_main.a to your /usr/lib folder
sudo cp *.a /usr/lib
This worked for me.