UPDATE: GDB 7.8 is now available through Homebrew and it can resolve at least some symbols now. There are some warnings, but it seems to work now. Fat executables are not supported however.
It turns out that the GDB available through Homebrew is the official GDB which is different from the Apple GDB that was available in previous versions of Xcode. The official GDB cannot resolve the symbols to the system libraries, thus causing the issues in the question. Copying over the Apple GDB from a previous install is a possibility as it contains Apple's modifications, however it is a much older version that the official GDB, and will produce many warning when first loading an executable on OS X 10.9 Mavericks (seems to otherwise work fine for now though).
It is unlikely Apple will be continuing GDB development, so until GDB fixes this issue, using LLDB seems to be the better solution. Here is an example.
$ lldb ptrace
(lldb) b ptrace
(lldb) r
And the breakpoint will stop execution at ptrace
.