Debug user space application with MMU

This may be related to troubles debugging. I am trying to print a stack trace from within the program, but that doesn't work either. I tried with a very simple non-threaded C program:

#include <stdio.h>
# include <execinfo.h>
# include <stdlib.h>
void print_trace() {
  void *array;
  size_t size;
  // get void*'s for all entries on the stack
  size = backtrace(array, 10);
  // print out all the frames to stderr
  fprintf(stderr, "trace size %zu:\n", size);
  backtrace_symbols_fd(array, size, 2);
  exit(1);
}
void baz() {
  print_trace();
}
void bar() { baz(); }
void foo() { bar(); }
int main(int argc, char **argv) {
  foo();
}

When I build this on my PC (Ubuntu 10.10 x86_64) I get a nice stacktrace:

gcc -g -rdynamic -o test_bt test_bt.c

trace size 7:
./test_bt(print_trace+0x19)
./test_bt(baz+0xe)
./test_bt(bar+0xe)
./test_bt(foo+0xe)
./test_bt(main+0x19)
/lib/libc.so.6(__libc_start_main+0xfe)
./test_bt

On Nios II Linux I just get this:

nios2-linux-gnu-gcc -g -rdynamic -o test_bt test_bt.c

trace size 1:

I've been trying to mess with compiler flags, but haven't found any magic so far. Any ideas?