Well if it pairs with other phones then it sounds like a compatability issue with that particula phone.

Do you have any odd characters in the phonebook names? Long shot but my be worth looking at.