Did you check the listener log at the time ORA-12535 occurs?

Remember to check the firewall and port open connections when you troubleshoot!