Here is a sample script to get you started. Copy this, paste into Script Editor, and compile (watch out for line breaks that wrap here but aren't supposed to!) Save as a "Script Application". The script application will take a file dropped on it and replace any spaces in the name with underscores. You can modify the first "AppleScript text item delimiters" line to any other character that is giving you problems, and replace the underscore in the second text item delimiter line with any other replacement character you want. You can also just stack up a series of replacements and do them all at once.
Once you get that working (on a sample file named using all the wild characters you expect to encounter), you have to negotiate the following: 1) accessing and changing the names on the server (possibly by copying to your desktop, deleting from the server, changing the names and copying back) and 2) setting up a repeat loop that will handle not only a number of files but the possibility of nested folders as well. Again, that can be lengthy, so I suggest you post the question to the AppleScript Users List, accessible from the AppleScript home page.
----- script begins. Watch for broken line wraps!
on open (somefile)
tell application "Finder"
set SomeName to name of somefile
set name of somefile to my replaceThisText(SomeName)
end tell
end open
on replaceThisText(Incoming)
--recognize divisions by spaces
set AppleScript's text item delimiters to {" "}
copy every word of Incoming to Outgoing
set AppleScript's text item delimiters to {"_"}
--put words back together divided by underscores
set Outgoing to Outgoing as string
--reset divisions to default for any other scripts
set AppleScript's text item delimiters to {""}
return Outgoing
end replaceThisText
-- ----- end script