I don't think it's about character sets since English characters are used in email adresses. Check if the dns server(s) defined in applications server's network settings work properly. Check if application server can resolve addresses skytel.com, msgnextel.com.mx, localizador.movistar.com.mx etc.
How: Write "cmd" in Start->Run, then execute nslookup
What i mean by application server is the windows server hosting sd application server. Check Windows' Local Area Connection's settings which dns server is defined (most probably another server), then change dns server to one that can resolve addresses above. If there is no other dns server you can define, make necessary domain definitions on currently used dns server.
Did you check "Email debug" in General settings->email part of administrator console? If you check that, you can find more information in application server log file "logserver.txt". Also filling the two logging email fields with a valid email address that server can send messages would help.