El Capitan and iCloud - Verification Failed, There was an error connecting to the Apple ID server

I haven't been able to get my Mac Pro Early 2008 running El Capitan to connect to iCloud anymore. I assumed it was just old and its time had come, but it looks like many portions of the iCloud service should still work. After troubleshooting, I performed a new install (which was another set of issues, up to and including the recovery disk not downloading for this exact same issue), but it is now freshly booted and giving me the exact same error.