IPhone 3GS-Contact saved in phone or messages not appear in Contacts

OK, have read other threads on this topic but no one seems to have solved it. To reiterate - You receive a call (or MMS) from someone who isnt in your Contacts. Within the phone (or Messenger) app you save this no & Create New Contact. If you then go into Contacts app - the new contact cannot be seen. If you search the iPhone the new contact is found - as a contact!?!? Its not a MobileMe Sync issue - that (finally?) seems to be working - although the new contact wont sync as its not in Contacts. Its also not a Groups issue.
I know there maybe a workaround by turning off the Contacts sync then turning it back on but thats a real pain.
Anyone got any progress on this problem???
iPhone 3GS iOS 4