What user are you running chmod as? You need to be logged in as root (or use su or sudo) to be able to change the permissions of sshd.
EDIT: I haven't had a chance to check whether you get the same error on read-only file-systems, but have you checked the partition is mounted read/write?
Also, this isn't the correct forum for this topic. You should probably ask a moderator to have it moved...
Last edited by gilead; 06-13-2007 at 07:59 PM.