It could be possible that it is your firewall or other internet 'security' tool which blocks it. Though that wouldn't explain why the server can be contacted if you test the settings or why you do get a popup when you sign in...
Plus!Live doesn't have an executable anymore as it is totally integrated/hooked into Windows Live Messenger.
If you follow all the nessecairy steps as you said you did, I'm afraid I don't have any clue to what the cause might be....
As alternative you could try this script:
"
[RELEASE] Gmail Checker 1.10 - get alerts upon new emails in your gmail accounts"
It does the same but connects in a different way.
/ 
