I had this problem about in March 2008 with version 7.42.
From the CM GUI if you select "Tools/Patch Analysis Config" on the Hotfix Config tab there will field named: choose depot hotfix folder
This would lead you to believe this is the location a user would need write access to in order to save patches. However, they may require more than that.
In our case this path was not the default value of Depot/Hotfix Repository.
Our users were granted write access to the non-default path, but continued to receive the error you're reporting until they were ALSO granted write access to the "Depot/Hotfix Repository" path.
If that doesn't fix it for you reference Ticket#24313 with support.