Okay, I'm a moron. Right after posting this thread, I checked all my setting again. The machine having the problem ended up having a flaw in it's Static IP settings which confused it about it's place in the world.

I deserve a flaming for this nonsense.

Flame on, anyone?