When trying to connect to my new Raspberry Pi via SSH, this only worked when done locally. It turned out to be caused by the /ect/hosts file. I had set the hostname using the raspi-config tool, which linked it with the loopback address instead of the real one (192.168.x.x). Changing it to the proper address solved the issue.