Hi
Try going to the serviceability page:-Tools - Control Centre - Network Services and restarting the license manager (under platform services) and then go back and try deleting 5 to 10 phones at a time. This may get you out of a jam.
I've just stumbled accross a similar problem with CUCM 5.1.3-3000-5 running on an HPDL380G5 server. This is our development server for which our Cisco SE kindly negotiated 100 user license so we would carry out proof of concept work and other development that might be deemed as too risky to try on the live service.
All was fine until I proved the validity of our backups by restoring them to the development server. The restore was fine but down side is that I now can't add any phones because I'm oversubscribed by about 3600 units. If I try and delete some, I get he same error message. Restarting the license manager does allow me to delete about 20 at a time but I've got 3600 to wade through.
Richard