If you get that for all ports, it may be a firewall on the Linux box. Have you used nmap from http://www.insecure.org/nmap/
before? There is a Windows version so you can scan the Linux box from Windows and see what ports are open.
One the Linux box, have a look in /etc/init.d for a file called iptables (or firewall, or something like that). Try, as root, running service iptables stop
and then run nmap again (or just try and telnet to the box).
It may be that telnet is disabled - it's not the best choice for remote access. Have you tried ssh?