Checksum to edit profile not working?
I believe that for profile edit, you need to use id rather than cid for the contact id, as per the docs you linked to:

http://www.myorganization.org/civicrm/profile/edit?reset=1&amp;gid=N&amp;{contact.checksum}&amp;id={contact.contact_id}