Cortana wont find any of my contacts?

[masonbogert]

When I try to use the text or call commands with Cortana, it won't recognize any of my contacts. I say "Text John Doe". It tells me "Sure, who do you want to text?". In the bottom it suggests "John Doe". I say John Doe, it auto capitalizes John Doe as a name, and then says "I can't find that contact". Is anyone else having this problem? These are synced Outlook.com contacts.

I'm on a Lumia 1520, just updated to 8.1.