Greg and I think we've figured out how to prevent the problem - ensure SFTP is set as the protocol when creating the connection. If it is not, then delete the connection and create a new one from scratch. Do not simply edit the protocol in the Edit Connection window.

Test results:

If I create a connection and specify SFTP at that time, then I can successfully publish php files.
If I create a connection and specify FTP, and then immediately edit that connection so the upload protocal is SFTP, then I cannot successfully publish php files.
So, Contribute must be configuring the permissions based on the protocol when the connection is created and then failing to modify the permissions configuration if the protocol is changed later. I'll do a bit more testing and let you know if I discover anything further.

Likely culprit:

In this folder

[currentUser]/Library/Application Support/Adobe/Contribute 4/Configuration

(note two space characters in that pathname)

is a file called ssh_hosts, which I'm guessing is at the root of the problem. Our theory is that file cannot be edited or can be edited in only certain ways, and that those restrictions explain the "permissions configuration fails to update when protocol changes from FTP to SFTP" problem. The other option is that there is simply some bug in Contribute causing it to fail to update the hash in that ssh_hosts file when the protocol is changed.