After reading some more forum threads today, i read a couple about DNS and IP resolution problems. Apparently this was my issue.
When I created package, it automatically "detected" the server name as the fully-qualified DNS name. However, there is no DNS pointed to this test server, the AES was attempting to resolve it as a full DNS name. The clients then had a server DNS resolution error in the log. When I changed the deployment package to point the correct server name, the clients received the licence and policy correctly.
If anyone else seems to have issues, you might check to make sure the server name is correct and that it has the correct IP or DNS name. I figured that the AES knew what it was doing. Apparently the AES just guesses, so double check the server name/IP in your deployment package if your server does not have full a full DNS record.
/* Thomas */