Well, it took a little wrestling with my ISP partner (whom is a MS guy), but I finally got him to agree that it's a routing issue and not my linux box (which he's apt to blame, most of the time).
We're going to reboot our router this morning and force a rebuild of the routing tables, and if that doesn't help, we go up the chain.
So, just so you guys know, we're on the issue. And, I hope to have us back to 100% soon!
I'll let you know something as soon as I know something, as always.
-Jason