Make sure you compiled the code with -fno-omit-frame-pointer gcc option.

This is an old question, but this in now possible with --call-graph dwarf. From the man page:

 -g
       Enables call-graph (stack chain/backtrace) recording.

   --call-graph
       Setup and enable call-graph (stack chain/backtrace) recording, implies -g.

           Allows specifying "fp" (frame pointer) or "dwarf"
           (DWARF's CFI - Call Frame Information) as the method to collect
           the information used to show the call graphs.

           In some systems, where binaries are build with gcc
           --fomit-frame-pointer, using the "fp" method will produce bogus
           call graphs, using "dwarf", if available (perf tools linked to
           the libunwind library) should be used instead.

I believe this requires a somewhat recent Linux kernel (>=3.9? I'm not entirely sure). You can check if your distro's perf package is linked with libdw or libunwind with readelf -d $(which perf) | grep -e libdw -e libunwind. On Fedora 20, perf is linked with libdw.

Man page of pref report documents the call chains display with children accumulation:

  --children
       Accumulate callchain of children to parent entry so that then can
       show up in the output. The output will have a new "Children"
       column and will be sorted on the data. It requires callchains are
       recorded. See the ‘overhead calculation’ section for more
       details. Enabled by default, disable with --no-children.

I can recommend you to try non-default mode with --no-children option of perf report (or perf top -g --no-children -p $PID_OF_PROGRAM)

So in default mode when there is some callchain data in perf.data file, perf report will calculate "self" and "self+children" overhead and sort on accumulated data. It means that if some function f1() has 10% of "self" samples and calls some leaf function f2() with 20% of "self" samples, then f1() self+children will be 30%. Accumulated data is for all stacks where current function was mentioned: for the work done in it itself, and work in all direct and indirect children (descendants).

You can specify some of call stack sampling method in --call-graph option (dwarf / lbr / fp), and they may have some limitations. Sometimes methods (especially fp) may fail to extract parts of call stack. -fno-omit-frame-pointer option may help, but when it is used in your executable but not in some library with callback, then call stack will be extracted partially. Some very long call chains may be not extracted too by some methods. Or perf report may fail to handle some cases.

To check for truncated call chain samples, use perf script|less somewhere in the middle. In this mode it does print every recorded sample with all detected function names, check for samples not ending with main and __libc_start_main - they are truncated.

otherwise the main function would have its children column not far from 100%

Yes, for single threaded program and correctly recorded and processed call stacks, main should have something like 99% in "Children" column. For multithreaded programs second and other threads will have another root node like start_thread.