I have a jtag-uart as part of my project, but I use one of the serial ports as the debug console.
When I ran into this problem, I was simply installing the same 5.0.1 tools I had on a new machine (quartus 5.0 web version + nios5.0.1 full version). I copied the two project folders and used the import feature to bring them in. Using "Run", the code ran as expected. Using "Debug", gave the RMT warning and some kind of variable dump in the IDE console window.
I later discovered that I could simply do a "resume" and the debug session would begin.
I also found that a newly created "hello world" project did not have the problem, which points to something wrong in the project files I imported.
Once I created a new project from scratch and copied my source files into it (different project name), the strange behavior went away.
A similar problem description exists on non-altera gdb/eclipse forums.
If you still have problems, I would make sure you have only one version of the altera tools installed.