You can add code to check for an empty string in the old value:

    If strOld <> "" Then
      wsData.Columns("B:B").Replace What:=strOld, _
        Replacement:=strNew, LookAt:=xlPart, _
          SearchOrder:=xlByRows
    End If

Hi

Debra's code was based upon a fixed range for Fruitlist, whereas I suspect
yours is Dynamic.
One way of dealing with the problem would be to test for a null string for
Old and goto the exit handler. I have marked where the inserted lines
appear.

Private Sub Worksheet_Change(ByVal Target As Range)
On Error GoTo errHandler

Dim rng As Range
Dim strOld As String
Dim strNew As String
Dim wsData As Worksheet
Dim wsLists As Worksheet

Set wsLists = Sheets("Lists")
Set wsData = Sheets("Data")
Set rng = wsLists.Range("FruitList")

If Intersect(Target, rng) Is Nothing Then
 'do nothing
Else
 Application.EnableEvents = False
 strNew = Target.Value
 Application.Undo
 strOld = Target.Value

' inserted lines
If strOld = "" Then
 Target.Value = strNew
  GoTo exitHandler
 End If
 ' end of inserted lines

Target.Value = strNew
 wsData.Columns("B:B").Replace What:=strOld, _
   Replacement:=strNew, LookAt:=xlPart, _
     SearchOrder:=xlByRows
 Application.EnableEvents = True
End If

exitHandler:
 Application.EnableEvents = True
 Exit Sub

errHandler:
 MsgBox "Change could not be completed"
 GoTo exitHandler
End Sub