Figured it out (I think)
Swapped network cards. I was using a Trendnet gigabit NIC before, with a REaltek RTL8169S-32 Chipset. I looked at dmesg and saw that it was installing Intel gigbait NIC drivers. Installed an older 10/100 Realtek w/8139 chipset, and now all is good. I am not sure if this warrants a bug report to the folks at Xen, as I am as mentioned before, a n00b, but if anyone thinks this warrants greater attention, let me know.
But I can SSH now. Hoo-ray.