If the restarts that alm1 don't work, you could try wiping the device and remove/re-add on the BES and try it again. I had to do this just this morning for a 7520 and it worked like a charm.
If I get a particularly cranky device, I will walk thru the 'old-fashioned' sync (syncing prior to BES 4.0) and then do the Enterprise Activation. Usually when I do the sync, I'll get the message that the encryption key is out of date, and that is probably what was holding up the EA. I just don't have any patience