Okay, I was able to fix it. As I expected, it was due to some servers being blocked in my hosts file. I thought it would have been gc.apple.com since Game Center connects to that when it starts according to Little Snitch, but that wasn't it. I deleted some entries related to VeriSign and a couple others and now Game Center works fine. I wish I could be more specific about which entry was the culprit, but I wasn't very methodical.
In summary, check your hosts file!