Outlook not sending emails.

I deleted my contact in my address book, but now when i try send an email, i get the following error message. Check Names- Microsoft Outlook doesn't recognize"....".
(between " " is the email address i am trying to send it too) I have tried reinstalling Outlook, repairing the pst file but it doesn't work. If i email an email address, i have emailed before it works fine but if i have never emailed an email address it gives me this error message? Any one got any ideas how to fix?

i am using outlook 2010

where in outlook? and change what?

it is already selected