If they are going to hash the data, they should salt it (and possibly use key strengthening a la bcrypt, etc).
The purpose of uploading your contacts is so that if Jack's phone number is (555) 555-5555, and Sam uploads a contact list saying that he is friends with a guy whose phone number is (555) 555-5555, Path can match up those two phone numbers (or hashed versions of them) and tell Sam that Jack is a member. That match-up doesn't work if the phone number is stored as (a hashed version of) 5555555555jack and 5555555555sam.
It wouldn't keep someone with access from checking if a social relationship existed in the database, but it should make recovering phone numbers and the like from the hashes quite a lot harder.
To be honest this should be a third party service, since it sounds like every major social networking app is doing the same exact thing.
(Hi Dan?)
Of course the other side would be maintaining users in this service, which again is pretty straight forward.
(Hi David?... I'm the OTHER DJB, probably not the one you are thinking of)