It took me additional 2 hours and the following links to finally get postfix start sending mail through gmail.
It was mainly settings of the account authentication that prevented sending out the emails, You may check the following links for details:

The last link have a critical component that without it I couldn't get the authentication with gmail to work!

You need to enable TLS in Postfix's SMTP client, since Google requires it. This is indicated by them in the message "Must issue a STARTTLS command".
In /etc/postfix/ you want something like this:
smtp_tls_policy_maps = hash:/etc/postfix/tls_policy

and then in /etc/postfix/tls_policy:
[]:587 encrypt

where the "[]:587" part must be identical to the "relayhost" entry in file

and you must run postmap on the policy file:
sudo postmap hash:/etc/postfix/tls_policy

now, finally after additional 2 hours of search and trial I have postfix and mailutils sending out emails,
I hope this may help others too.