Cannot connect to SSH server from Mac OSX

Whenever I try to connect to a remote server using SSH, I get an error "ssh: connect to host x.x.x.x port 22: Connection refused"

I didn't install a Firewall or something similar. I know for sure the server is online and my credentials are valid - I am able to connect to the server using my (Android) phone or other devices.

Is there any way that connections are blocked by the System? This also happens for some other applications on different ports and servers.

Do you have any ideas how I can troubleshoot the problem? I can browse the Internet without any problems, but SSH and some other applications can't connect to different servers with different ports, including a Usenet client.

Happens on a Macbook Pro Late 2011 using MacOSX Yosemite.

If you need any more information, don't hesitate to ask.