Email not working with postfix

I have a fresh installation of Debian 7 which I have installed GitLab on with omnibus. I followed the instructions, installing openssh and postfix first then installing gitlab. Everything works fine except GitLab will not send out emails when a new user is created. I have looked all over and have not found any answers. I began troubleshooting postfix itself but from what I can see it is working just fine. I can send emails with postfix directly. Can anyone point me in another direction to look of why this wouldn’t be working.
Thanks for looking.

Did you ever figure this out? I have just about the same problem. Would be really great to have some simple instructions for connecting Gitlab with a working Postfix install. Reading through outdated search results for hours and hours isn’t much fun!

Same issue.
Posted here too: http://superuser.com/questions/1179980/postfix-errors-in-gitlab-instance