Weird behavior with Contacts creation and Exchange syncing

[theNEOone]

When I save a contact from a text messaging queue or recent call log using the iPhone's built-in Save Contact button, my phone will allow me to create/add the contact, but won't retain it in the "normal" address book place. It's as if the contact gets lost somehow. For whatever reason, the contact be be located by searching for it using search/spotlight on the iPhone, but it doesn't appear in the phone's address book, nor does it sync to my online Gmail contacts or my Mac's address book. However, if I create a contact on my Mac or "manually" on the iPhone, it will behave correctly. WTF?? .

Any ideas???

iTunes 9.1.1
OS X 10.6.3.
iPhone OS 3.1.3