Going to https://accounts.google.com/DisplayUnlockCaptcha
and then retrying the operation, worked a treat!

Thank You Pablo.

I was having a similar problem and i solve it changing the order of the settings.
It worked exactly like this

EMAIL_USE_TLS = True
EMAIL_HOST = 'smtp.gmail.com'
EMAIL_HOST_USER = "xxxx@gmail.com"
EMAIL_HOST_PASSWORD = "xxxxxxxx"
EMAIL_PORT = 587

You can try it easy with the django shell:

>>> from django.core.mail import send_mail
>>> send_mail('test email', 'hello world', 'xxxx@gmail.com', ['xxx@yyyy.com'])

hope it helps

What do the error logs show? Do you have a firewall in place, by chance?

No firewall, currently; just a minimal install to try things out.

Internal Server Error: /contact/
Traceback (most recent call last):
File "/usr/local/lib/python2.7/dist-packages/django/core/handlers/base.py", line 114, in get_response
response = wrapped_callback(request, *callback_args, **callback_kwargs)
File "/usr/local/lib/python2.7/dist-packages/django/views/generic/base.py", line 69, in view
return self.dispatch(request, *args, **kwargs)
File "/usr/local/lib/python2.7/dist-packages/django/views/generic/base.py", line 87, in dispatch
return handler(request, *args, **kwargs)
File "/opt/officeowlsproject/officeowls/source/contact/views.py", line 39, in post
form.cleaned_data['message'])
File "/opt/officeowlsproject/officeowls/source/contact/views.py", line 49, in send_notification_mail
send_mail(subject, message, settings.EMAIL_HOST_USER, [settings.EMAIL_HOST_USER])
File "/usr/local/lib/python2.7/dist-packages/django/core/mail/__init__.py", line 50, in send_mail
connection=connection).send()
File "/usr/local/lib/python2.7/dist-packages/django/core/mail/message.py", line 255, in send
return self.get_connection(fail_silently).send_messages([self])
File "/usr/local/lib/python2.7/dist-packages/django/core/mail/backends/smtp.py", line 88, in send_messages
new_conn_created = self.open()
File "/usr/local/lib/python2.7/dist-packages/django/core/mail/backends/smtp.py", line 55, in open
self.connection.login(self.username, self.password)
File "/usr/lib/python2.7/smtplib.py", line 613, in login
raise SMTPAuthenticationError(code, resp)
SMTPAuthenticationError: (534, '5.7.14 Please log in via your web browser and then try again.\n5.7.14 Learn more at https://support.google.com/mail/bin/answer.py?answer=787\n5.7.14 54 c1sm9978624qad.1 - gsmtp')

Make sure the password is correct. If it is, check out the last 2 answers in Net::SMTPAuthenticationError when sending email from Rails app (on staging environment) | Stack Overflow or this GitHub issue: Error: Net::SMTPAuthenticationError in RegistrationsController#create when signing up.