I do have root access to my dedicated server, loging in like that generates the message, I also tried sftp login with one of the accounts (while shell access was enabled for the account) but no good either.
I did find report about problems with OpenSSH on Mac, could this be related?
Well, shell access (SSH) is not the same as SFTP. The SFTP protocol runs on top of SSH. The message implies that the SFTP server is simply not available or installed. Again, your server provider should have the answers here.
The OpenSSH installation that comes as part of Mac OS X doesn't have any issues that I am aware of. But if you have installed a custom version then all bets are off. Don't do that.