Sometimes ADE gets its registration/activation confused and in a semi-authorized state..
Try completely removing any authorization using ctrl-shift-D to ADE (cmd-shift-D if on Mac).
Restart ADE, and then reauthorize with your Adobe ID.
Even after doing what you suggested, ADE still does not connect to the fulfillment server. It is telling me to make sure I am connected to the Internet, even though I am.
Two more suggestions:
Try with firewall (and maybe even antivirus) temporarily switched off.
There are lots of bugs in ADE2.0. Try replacing ADE2.0 with the older but more reliable v1.7.2.
Version 1.7.2, it is a little difficult to find, available on Adobe site for Windows and for Mac.
The forum software is sometimes corrupting the link above. There shouldn't be a blank in 'editio ns.html'. The following redirects to the same page: http://tinyurl.com/diged172