Você precisa usar o método "Worksheet_change" para alterar a formatação quando novos dados forem adicionados.
Private Sub Worksheet_Change(ByVal Target As Range)
If Target.FormatConditions.Count = 0 Then
<add your code here>
End If
End Sub
Eu não tenho muitas experiências com formatação condicional no VBA. Talvez a criação de uma nova condição toda vez que os dados forem adicionados acabará em muitos grupos de formatação quando você abrir o menu Formatação condicional. Para mantê-lo como uma formatação, talvez seja necessário definir sempre a formatação para todo o intervalo ( set rng=Range("A1:A" & target.row)
).
Solução livre VBA: se você converter seus dados em uma tabela (tabela de inserção do EXCel 2007), na medida em que os usuários adicionarem as linhas imediatamente abaixo dos dados existentes, suas fórmulas e formatações condicionais serão automaticamente transferidas para a nova linha também.