make sure the gcov and gcc are of the same version :), this where many of the people fail to check.
$gcc --version
gcc (GCC) 4.1.1
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ find /usr/lib/gcc -name libgcov.a
/usr/lib/gcc/x86_64-redhat-linux/4.1.1/32/libgcov.a
/usr/lib/gcc/x86_64-redhat-linux/4.1.1/libgcov.a
/usr/lib/gcc/x86_64-redhat-linux/3.4.6/32/libgcov.a
/usr/lib/gcc/x86_64-redhat-linux/3.4.6/libgcov.a
so the gcc version you have loaded should be atleast in the available list of libgcov.a