under settings, click accounts - > your email and accounts.
click on Gmail (it should show your gmail email address) and then should show a button manage. click Manage
Should now have a screen that says Gmail account settings.
click on Change mailbox sync settings
scroll to the bottom and make sure contacts is set to ON.
if its Off, you will not get any contacts from that account to your windows phone.
let me know if that helps or if you need screen shots.
I had this. I see all my Gmail contacts in People HUB, but when I send email through Outlook, it do not find this Gmail contact. So I have to go into People hub, search contact, copy email and paste it in Outlook.