Hi Equinox,
I don't know what can be your problem.
I have used the example code above and it was working well with my hardware: pc hyperterminal <-> ftdi chip <-> nios with fifoed uart.
maybe read again the documentation:
http://www.alterawiki.com/wiki/fifoed_avalon_uart set the same rate at both side of the uart and try first a slow rate.
If it still doesn't work you can try to instantiate 2 uarts in a nios then connect them together (uart1_rx<->uart2_tx / uart1_tx<->uart2_rx).
Then in a nios software project try to send data and receive data, maybe only a simple char first.
It will help you to understand how it works.
good luck.