Using a VBScript.RegExp will greatly help clean your algorithm:

Static reg As Object
If reg Is Nothing Then
    Set reg = CreateObject("VBScript.RegExp")
    reg.Pattern = "(?:^(?=\d)|\W)" 'A Digit at the start or any illegal character
    reg.Global = True 'Replace all matches
End If
Namify = reg.Replace(inputName, "_")

This does the same as your entire function. Read more about RegExps here

Using a VBScript.RegExp will greatly help clean your algorithm:

Static reg As Object
If reg Is Nothing Then
    Set reg = CreateObject("VBScript.RegExp")
    reg.Pattern = "(?:^(?=\d)|\W)" 'A Digit at the start or any illegal character
    reg.Global = True 'Replace all matches
End If
Namify = reg.Replace(inputName, "_")

This does the same as your entire function. Read more about RegExps here

If you additionally write a function ContainsName(name As String) As Boolean wich traverses ActiveWorkbook.Names and returns True if name is a valid name, you can add an additional feature to generate a valid new name as Mat suggests:

Static trailingNum As Object
Dim number As String
If trailingNum Is Nothing Then
    Set trailingNumm = CreateObject("VBScript.RegExp")
    trailingNum.Pattern = "\d*$"
End If
While ContainsName(Namify)
    number = trailingNum.Execute(Namify)(0).Value
    If Len(number) = 0 Then number = "0"
    Namify = trailingNum.Replace(Namify, CStr(CInt(number) + 1))
End While

Using a VBScript.RegExp will greatly help clean your algorithm:

Static reg As Object
If reg Is Nothing Then
    Set reg = CreateObject("VBScript.RegExp")
    reg.Pattern = "(?:^(?=\d)|[^a-zA-Z0-9_])" 'A Digit at the start or any illegal character
    reg.Global = True 'Replace all matches
End If
Namify = reg.Replace(inputName, "_")

This does the same as your entire function. Read more about RegExps here

Using a VBScript.RegExp will greatly help clean your algorithm:

Static reg As Object
If reg Is Nothing Then
    Set reg = CreateObject("VBScript.RegExp")
    reg.Pattern = "(?:^(?=\d)|\W)" 'A Digit at the start or any illegal character
    reg.Global = True 'Replace all matches
End If
Namify = reg.Replace(inputName, "_")

This does the same as your entire function. Read more about RegExps here