The may be other formating besides Font size in  your header.  for eample

$D&10MyHeader    &10 is font size 10

there are two fromats in the header.  You have to strip out the 2nd
formating and replace with &14.  Try this code

Sub Fix_Headers()
'
' Macro1 Macro
' Macro recorded 5/12/2008 by jwarburg
'

'
For Each sht In ThisWorkbook.Sheets
   With ActiveSheet.PageSetup
       .LeftHeader = fixfont(.LeftHeader)
       .CenterHeader = fixfont(.CenterHeader)
       .RightHeader = fixfont(.RightHeader)
   End With
Next sht
End Sub
Function fixfont(header)

fixfont = ""
Do While InStr(header, "&") > 0
  If IsNumeric(Mid(header, 2, 1)) Then
     'character after amphersand is a number
     'check if the old font size is one or two digits
     If IsNumeric(Mid(header, 3, 1)) Then
        'old font is 2 digits
        'remove old font size
        header = Mid(header, 4)
     Else
        'old font is 1 digits
        'remove old font size
        header = Mid(header, 3)
     End If
     fixfont = fixfont & "&14" & header
     header = ""
  Else
     'remove amphersand other formats
     If InStr(2, header, "&") > 0 Then
        'remove first format string
        fixfont = Left(header, InStr(2, header, "&") - 1)
        header = Mid(header, InStr(2, header, "&"))
     Else
        'there are no more amphersand, add font
        fixfont = fixfont & "&14" & header
     End If
  End If
Loop

End Function