For me, fixing this problem just meant reading more carefully!

I am updating some shared contacts via the Google Apps Shared Contacts API and curl. I was able to create new shared contacts with no problem, but unable to update an existing contact. The answer to the problem was to use PUT instead of POST when updating an existing entry. It's right there in the documentation, I just needed to pay more attention to the details.