Question: Consider the following scenario:

I have a Debian-ssh-server setup and exposed it to the internet for some time for testing. Also I have an account which is basically configured as root in the `sudoers` file (I know this is poorly mis-configured!) and of course no root login is permitted. The authentication is password and not key based.

What happened is the following, I have set up the server from my own laptop and I could login to this account from anywhere, at home of course and even from other networks. But as I tried to login from another machine I got the 'access denied' message.

What grinds my gears is why could I login from my home machine, the access should have been denied either, shouldn't it?

Answer: 
Open the file `/etc/ssh/sshd_config` and change the next line:

```
PermitRootLogin without-password

```

with:

```
PermitRootLogin yes

```

Finally, reboot the server.
You should look at multiple things:

1. Look at the log files on the server: `/var/log/auth.log`, `/var/log/secure` as [Jenny](https://unix.stackexchange.com/users/21109/jenny-d) did propose in her [comment](https://unix.stackexchange.com/questions/109574/ssh-access-denied-from-one-host-but-not-the-other/109577#comment169041_109577).
2. Configuration of your ssh ( `/etc/ssh/ssh_config` on your client machine ), it might be set not to use password authentication ( entyr `PasswordAuthentication` set to `no`).
3. Start `ssh` with `-v` option (`ssh -v`) to get verbose output
4. Configuration of the sshd ( `/etc/ssh/sshd_config` ) on the server. It could only listen to connections coming from certain IP addresses ( e.g. the one from you router ).

If you can, try to login from the client to another machine, that way you can pinpoint which of both machines is the problem (although they might be both the problem).