This is likely something that you will want to open a support case for. But I do have a couple of things to look at.
The first question to ask when you are diagnosing a license server probem is "Is the device contacting the license server"? This is pretty simple to look into on the license server side. Just log into your license server client, and go to the Status page. On the status page, you will see a list of Unlicensed Devices. Is the device you are working on in this list?
If the device is not showing up, that tells us that there is a communication problem. You will want to verify that the device is on the wireless network, and that no other applications are using or blocking the licenser server port (1820 UDP by default).
If the device does show up, you can say that the connection is good.
The next step is to verify what type of license the device needs. Under Unlicensed Devices, you will see what the device needs under the Platform requested property. In the example above, the device is asking for TelnetCE 7.0 WEB. You will want to check your licenses to make sure you have some licenses with that platform version available.
There is often times a mismatch between what the license was registered for vs what version of the client was installed on the mobile unit. For example, if I installed TE version 7.0 on the device, but I registered my license for 7.2, the device will give the license server error. You can rectify this be either installing a version of the client on the device that matches the license, or re-registering the license (you will have to open a support case for the second option).
I hope this helps. If you need further assitance, please open a support case and we will work with you further.