There is a bug hidden somewhere in the depths of gdb-6.0-r1, which causes gdb to be unable to debug all binaries, regardless of their stripped/unstripped status. Upgrading to gdb-6.3 fixes the problem, but that requires ~amd64. I'd suggest 6.3 get marked "amd64" rather than "~amd64" unless a patch can be tracked down for 6.0. The URL links to a forum thread where the user describes the exact same problem I experienced. I experienced this problem with all binaries, even ls, and simple hello world applications.
6.3 is stable now