Have you tried using the healing brush AFTER using the clone tool. Usually, if the clone isnt enough, the healing brush works pretty well. Sometimes you have to do small sections at a time, but usually that works.