I think I finally solved the problem. The above fixed Safari's cookie error but no other app was connecting. I was researching a different issue and realized I needed to check my LaunchAgents and LaunchDaemons which seemed like the type of thing that would be causing this problem. Also a few kernel extensions that seemed extraneous. I deleted the following and now all apps seem to connect fine:
/Library/LaunchAgents/com.adobe.AAM.Updater-1.0.plist
/Library/LaunchDaemons/at.obdev.littlesnitchd.plist
/Library/LaunchDaemons/com.adobe.SwitchBoard.plist
/Library/LaunchDaemons/com.adobe.versioncueCS3.plist
/Library/LaunchDaemons/com.microsoft.office.licensing.helper.plist
/Library/Extensions/LittleSnitch.kext/
~/Library/LaunchAgents/com.adobe.AAM.Updater-1.0.plist
~/Library/LaunchAgents/com.adobe.ARM.df0ab5bbe6f698196fcc21e3c1e66dcb758bd911f4d 637272d9d8109.plist
~/Library/LaunchAgents/com.spotify.webhelper.plist
~/Library/LaunchAgents/com.valvesoftware.steam.ipctool.plist
I think that was everything. The likely culprit would be Little Snitch but I wasn't running it (though I did use it to troubleshoot this issue months ago) so maybe something was corrupted and interfering in the background. None of the user items seem like they would really cause this, but it is strange that I wasn't getting the problem when I created a new user but when I copied my user folder over it started again. So I would think it was in the user folder, but who knows. It's working for now.
One other thing, the problem I was having with uTorrent was actually an unrelated problem that had to do with flushing the files to disk, apparently the version of uTorrent I was using gets caught up while writing and slows itself down automatically. But when I mentioned above that it wasn't working, it would say "cannot connect to host" at all and then miraculously would start connecting hours later (like Mail and Skype would). Just wanted to clarify that if anyone uses this for future reference.