$ cat test.c
#include <stdio.h>

int main(int argc, char** argv) {
  int i;
  for (i = 0; i < argc; ++i) {
    printf("argv[%d] = \"%s\"\n", i, argv[i]);
  }
  return 0;
}

$ rm -f test.gcda
$ gcc -o prof -fprofile-arcs test.c
$ ./prof
argv[0] = "./prof"
$ test -f test.gcda && gcc -o final -fbranch-probabilities test.c
test.c: In function ‘main’:   test.c:9:1: note: file $PWD/test.gcda not found,
execution counts assumed to be zero

Identified the relevant command via strace and ran it through gdb:
$ gdb --args /usr/libexec/gcc/x86_64-pc-linux-gnu/4.5.2/cc1 -quiet test.c \
  -D_FORTIFY_SOURCE=2 -quiet -dumpbase test.c -mtune=generic -march=x86-64 \
  -auxbase test -fbranch-probabilities -o test.s
It appears that coverage_init does not call read_counts_file because flag_profile_use is zero. So cc1 doesn't even attempt to read the file for which it claims it wasn't found.

It appears that this is a problem introduced by gcc 4.4.0 in this commit:
http://gcc.gnu.org/viewcvs/trunk/gcc/coverage.c?r1=133773&r2=133774

GCC version is "gcc (Gentoo 4.5.2 p1.1, pie-0.4.5) 4.5.2", my system is x86_64-pc-linux-gnu. The Gentoo build was configured using USE=vanilla, so there should be no Gentoo-specific patches involved. If you have any trouble reproducing the issue, let me know and I'll see what other details I can provide.