OK so I have solved this and thought I should add the solution to here for others that may end up in the same situation.
Apparently the client I was trying to connect with was mentioned in the file
I deleted it from there and I could then connect to the SSH server!
Though, a few hours later it did not work again. I checked the
/etc/hosts.deny file again and my client was again added to the file!
Some digging further lead me to the
/var/lib/denyhosts/ directory which has the files:
hosts-restricted where my client was mentioned. I think it has to do with me entering the wrong password too many times, and then it just kept on repeating everytime I tried to do a bad login.
In the config file
/etc/denyhosts.conf you can define settings for this and what should happen if someone gives the wrong login etc. In my case, the reason why it worked sometimes and sometimes not, was because the ban was removed after 5 days. Now I just commented it out so whenever someone is banned, the client will be banned forever until I unlock it myself. I also set up so that an email will be sent to myself whenever someone gets banned.
I hope this helps someone else too!