OpenSUSE Network :: SSH Working For External But Not Internal?

I have a SuSE server (sorry but no idea what version of SuSe it's running.. I'd take a guess at 10.0) on a network with several other SuSE servers. They are all able to be SSHed externally as well as internally and all have their local firewalls disabled. I just had to reboot one of the servers and it is behaving quite strangely. I am able to SSH in and out of it externally, but can't SSH in and out of it internally.

When trying to SSH out internally I get the message:
"ssh: connect to host *.*.*.* port 22: No route to host"
When trying to SSH in internally I get the message:
"ssh: connect to host *.*.*.* port 22: Connection timed out"
Using ssh -v doesn't give any more useful information.

I have double checked that the IP is correct and that the internal firewall is disabled etc. The external firewall hasn't got anything that would prevent it (and shouldn't be an issue anyway as it's an internal only problem... SSH externally works fine). Also, it might help to know that I have the same problem with ping. I can ping this server from an external system, but not from an internal one.