Ok, I was able to resolve the issues. I narrowed down the problem by disabling wi-fi and plugging directly into my cable modem with a LAN cable instead. While plugged straight into the modem (bypassing my router) XAT worked as normal and never asked me to prove I was human. I then turned wi-fi back on and tried it again connected wirelessly and got the prove you're human messages again. I did a factory reset on my router, and then put all the settings back the way I had them, and it seems that the problem has been fixed.
For some reason, my router decided to start blocking my XAT sessions on it's own. A factory reset seems to have done the trick.
Thanks for all your help and suggestions, everyone.