So did you try to keep nios2-terminal (or some other communication program listening on your com port) up and running before uploading your program to your development board first? That will definitely guarantee that if anything comes out on the UART from the dev board it'll be noticed.
As per your other questions.
I'm sorry, but I can't help you with# 1 until I have more information.
For# 2 We don't provide a telnet application. I would suggest that you take a look inside the busybox application that we do ship. I believe it might have a telnet client that work under Nios II. For more info, take a look inside the reference guide for Nios II Linux. It contains all the info you need to build busybox and upload it to your linux system.
For# 3, the Mtx Cyclone Board's Kitchen Sink example design is capable of running Linux. There are a number of example designs that come on the Microtronix Cyclone Board Development Board... those are all the ones we provide. If you have any specific hardware questions we might be able to help you.