Access not granted for user '...'.

[Cheeseboy]

Hi Nader,

This is just a hunch:
Look into ~/.ssh/config or /etc/ssh/ssh_config and the AddressFamily directive.
The man page (ssh_config(5)) doesn't tell which one is default, but I can imagine it defaults to IPv4 only...
Your auth.log message shows a IPv6 address.

Cheers,

Cheeseboy

[nader]

Finally I figured it out. My remote IP was in fact listed in the /etc/hosts.deny, interesting enough, each attempt was logged in auth.log too.

[Eek]

Did you open the ssh port in the firewall?
You might also consider moving the port from 22 to another number, say 2222
As a lot of people are searching for port 22 and trying to break in.

[Ubi]

moving the port is a good idea, but moving it to a number over 1024 enables spoofing by local users. Port 666 is a very good alternative (Doom port)

[Cheeseboy]

Port of the beast?

[Ubi]

Yes. Here be dragons.