OK, assuming the CALs were correctly entered in the License Manager, I've seen this sort of problem in a couple of circumstances:
1. Has the server been installed (or re-installed) from commercial media, or from an NFR disk, like from MSDN (seen this where the original disk was lost).
2. Has the PDC in the domain swapped places with a BDC recently?
If 1, reinstall from commercial media. No way round it, since NFR media is locked to 5 connections.
If 2, see Microsoft Knowledgebase articleQ142046 (http://support.microsoft.com/support/kb/articles/Q142/0/46.asp?LN=EN-US&SD=gn&FR=0&qry=License%20Manager%20Domain%20Controller%20promoted&rnk=1&src=DHCS_MSPSS_gn_SRCH&SPR=NTS40) for details on rectifying this.
Another possibility is that for whatever reason, the License Logging Service may be crashing on one or more of your servers. If none of these help, please let me know.