The symbols are taken from the dynamic symbol table; you need the -rdynamic option to gcc, which makes it pass a flag to the linker which ensures that all symbols are placed in the table.
(See the Link Options page of the GCC manual, and / or the Backtraces page of the glibc manual.)