prova questa:

codice:
Sub SostituzioneStringa()
    Dim sh As Worksheet, trg As Range, CountBlank As Double
    Dim sWhat As String, sReplace As String
    Cells(1, 1).FormulaR1C1 = "qui scrivo albero perché devo sostuituirlo"
    sWhat = "albero"
    sReplace = "faggio"
    For Each sh In Application.ActiveWorkbook.Worksheets
        If sh.Name <> "Protetto" Then
            On Local Error Resume Next
            Set trg = sh.Range("A1:IV65536")
            CountBlank = Application.WorksheetFunction.CountBlank(trg)
            If CountBlank < 16777216 Then
                trg.Replace What:=sWhat, Replacement:=sReplace, LookAt:=2, SearchOrder:=1, MatchCase:=False, SearchFormat:=False, ReplaceFormat:=False
            End If
            Set trg = Nothing
        End If
    Next
End Sub
l'ho testata e funziona su excel 2002

secondo me era il valore di LookAt che sbagliavi a passargli alla funzione Replace.... infatti:

1 - gli si dice a excel che tutta nella cella deve esserci quel valore esatto;
2 - gli si dice che excel di guardare la cella, se una parte di essa contiene il valore lo sostituisce...

fammi sapere