I had the same problem a while back.  This was the solution I was given which 
worked, but is a bit of a pain if you have a lot of licenses!  I am on version 
7.1.3

Solution Title: Decommissioned clients still consuming backup licenses
 
Solution ID: legato68096
 
Here is the solution: 
 
Ensure that there no clients still defined in the backup server, which are now 
decommissioned.

Compare the number of clients defined on the backup server VS the number for 
clients that exist in the backup server Client File Index structure (i.e. 
/nsr/index directory). You may use nwadmin =>indexes tab or from the "nsrls" 
command and then compare it to number of defined clients in the index directory.

If index directory has more client's in it than from nwadmin=index tab or nsrls 
command then delete the "NON-EXISTING" client's index folders.

Once you have removed the non-existing clients, 

a) Remove all of the licenses from the backup server
b) Shutdown NetWorker
c) Startup NetWorker
d) Re-install the enabler codes removed from step (a)
  
Here is the problem or goal:
 
Number of connected clients do not exceed number of available licenses
  
Problem with license
  
Error: 'save: RAP error: Unable to grant SERVER (UNIVERSAL) CLIENT license to 
client (Client_Name): Too many clients. Maximum is (Number)'
 
Problem Environment:
 
NetWorker 7.1.2
  
Has more licenses than connected clients
 
Causes of this problem:
 
Decommissioned clients still consuming backup licenses

+----------------------------------------------------------------------
|This was sent by martin.smith AT unitypartnership DOT com via Backup Central.
|Forward SPAM to abuse AT backupcentral DOT com.
+----------------------------------------------------------------------

To sign off this list, send email to listserv AT listserv.temple DOT edu and 
type "signoff networker" in the body of the email. Please write to 
networker-request AT listserv.temple DOT edu if you have any problems with this 
list. You can access the archives at 
http://listserv.temple.edu/archives/networker.html or
via RSS at http://listserv.temple.edu/cgi-bin/wa?RSS&L=NETWORKER