It's because those "empty" cells in column B aren't actually empty.
Using your attached workbook and code as an example, you can force the empty strings to be cleared from the cells like this:
Code:
Sub Example()
With Sheet1
'get rid of any null strings stored in the cells
With .Range("A1:L15")
.Value = .Value
End With
With .Sort
'set up the sort fields
With .SortFields
.Clear
.Add Key:=Sheet1.Range("A1:A15"), _
SortOn:=xlSortOnValues, _
Order:=xlAscending, _
DataOption:=xlSortNormal
.Add Key:=Sheet1.Range("B1:B15"), _
SortOn:=xlSortOnValues, _
Order:=xlAscending, _
DataOption:=xlSortNormal
End With
'set up the rest of the sort and apply
.SetRange Sheet1.Range("A1:L15")
.Header = xlNo
.MatchCase = False
.Orientation = xlSortColumns
.SortMethod = xlPinYin
.Apply
End With
End With
End Sub