All of my traces, regardless of where I try and connect from end like this:
12 core-01.ge-1-1.sfo1.gni.com (184.108.40.206) 10.237 ms 9.709 ms 9.702 ms
13 router-edge1a.threerings.net (220.127.116.11) 10.845 ms 12.148 ms 11.778 ms
14 router-edge1a.threerings.net (18.104.22.168) 11.391 ms !H 10.998 ms !H 15.374 ms !H
Line # 14 is where you see the problem. The !H stuff.
That's the router saying, essentially, "I can't find the host on the inside"
It can be caused by routing table issues on the router. I.E. someone fed their router crap info. Considering it started happening last night, I don't suspect that's the problem.
It can be caused by a failed link between the router and the inside firewall or switch, or whatever the "next hop" is for connecting to the game server. I don't know their layout, so can't say. However, if it was a bad cable, card, etc, I suspect it would have been found fairly quickly as well.
What that leaves us with is a problem either on the firewall itself (Possible) or with the internal LAN segment (another possibility)
The one thing I find odd is that of all the oceans except malachite are not responding on port 4007 (the YPP game port)
~$ telnet midnight.puzzlepirates.com 4007
~$ telnet cobalt.puzzlepirates.com 4007
~$ telnet sage.puzzlepirates.com 4007
~$ telnet malachite.puzzlepirates.com 4007
telnet: Unable to connect to remote host: Connection refused
But Malachite is actively telling people "Get Lost"
I'll keep digging into this, and provide updates here, unless people think it's not appropriate.