I was eventually BANNED FROM NETWORK! :)
I though I had some apps like Dropbox hugging the network, but it did not seem like it.
I have read that connecting to external DNS, not your Internet Provider's DNS, servers might speed up the lookup.
I got this list from support.hidemyass.com
To do so I got to:
Apple > System Preferences.. > Network > Wi-Fi (Connected) > Advanced .. > DNS