The reason it always shows the first A is that the code expects there to be column headers e.g. "Last Name", "First Name", "Address", "City" etc.
To unlock all cells run the Macro again but leave the input blank.
However, in order to conform with your whacko-iness here is code that will highlight the selections (you can put in as many characters as you want so if you are looking for a particular name you can enter the full last name)
Application.ScreenUpdating = False
Res = InputBox("Enter a letter to filter on (leave blank to see all)", "Filter Critera")
Q = """"
NChars = Len(Res)
LRow = Range("A2").End(xlDown).Row
Range("A1:M" & LRow).Select
Selection.FormatConditions.Add Type:=xlExpression, Formula1:= _
"=LEFT($A1," & NChars & ")=" & Q & Res & Q
.PatternColorIndex = xlAutomatic
.Color = 65535
.TintAndShade = 0
Selection.FormatConditions(1).StopIfTrue = False