Você não está usando o elemento Subfolder
em seu loop.
Uma solução recursiva alternativa está abaixo:
Set objFso = CreateObject("Scripting.FileSystemObject")
Browsefolder objFso.GetFolder("C:\Users\user\Desktop\test")
Sub Browsefolder(Folder)
For Each Subfolder In Folder.Subfolders
Browsefolder Subfolder
Next
For Each File In Folder.Files
sNewFile = File.Name
sNewFile = Replace(sNewFile, "ç", "+")
If (sNewFile <> File.Name) Then
File.Move (File.ParentFolder & "\" & sNewFile)
End If
Next
End Sub