Nios-II SOPC UART delivers wrong bytes

It certainly sounds like a hw problem, but to prove that it is not SW/timing related, you should use the simplest possible single-threaded test code. Just take the hello_world example and modify it to echo back everything it receives. Open the uart twice, once for read and once for write. Use a Y cable so a PC (not a scope) can be used to independantly monitor what is really going into the uart. For multi-tasking apps in particular, you should increase the default 64 char buffer size in altera_avalon_uart.h