Hi All
I had erased all the contacts from my Iphone manually and then tried to re sync all the contacts through outlook but failed, Tried a no. of times but couldn't get through
Finally I exported all my contacts to Yahoo Address Book and Synced My Iphone through Yahoo
& It worked just fine, Though its not the perfect way to Sync contacts as contacts keep on changing but this is also one of the way to do it.
Its working for me

yeah for me it works very fine with Y! address book.

i just miss the calendar to sync with yahoo too, it only syncs with outlook, so bad.