Mavericks iMessage & Facetime login problems

I am having another version of the prominent iMessage and Facetime login issues (getting message: Could not sign in. Please check your network connection and try again). Although I can't be sure , I think I've had this issue since Mountain Lion as I can't recall ever being able to login successfully but have never trouble shooted the problem until now, so my version of the problem may not necessarily be related to Mavericks.

In the past, when I was not able to get my MacBook Pro (mid-2009) connected, I just let it be since I didn't have the time to troubleshoot my routher settings etc. Recently, due to a HD failure, I installed a new HD and reinstalled Mavericks. During this process, I also upgraded my old desktop (iMac mid-2008) to Mavericks and discovered that it had no trouble connecting to iMessage/Facetime. Therefore the problem is clearly with my MacBook Pro - not with my router/server (if I am deducing correctly).

While I am not computer illiterate, I am not as well-versed as many of the pros on these forums, so keep this in mind as I recount what I have done so far (in no particular order):

-Checked GameCenter, I can login to this without trouble

-Reset PRAM/NVRAM (I suspect this may be moot with Mavericks, but hey, it was worth a try)

-Deactivated Firewall, restarted, tried login. This didn't work

-Deleted relevant plist files (FaceTime & iMessage), restarted. No login possible.

-Logged into Guest account on my computer, still couldn't log in.

-Deleted, reset Keychain, still no success. De-linked from iCloud also.

-Got more familiar with Console. It seems that I keep getting 'apsd[67]: Unrecognized leaf certificate' in the process, and 'identityservicesd[221]: [Warning] IMSetKeychainData: -67808 -- Could not store data for service: com.apple.facetime' during the attempted logins.

I have probably tried a few other things that I have forgotten, but that's the bulk of the efforts. I am guilty of having installed Sophos and a few other freeware utilities that I have now deleted - it is entirely possible that one of those apps messed things up.

Any help appreciated.

Thanks Community!