Can not Delete printers from XP Pro Domain Computers

Ok, this one leaves me scratching my head!

Background history as to when the problem began...

I have a client who we recently upgraded their only Domain Controller to a
Windows 2003 Server from a 2000 Server. Because the customer wanted to
implement a number of changes it was done was to build a temp 2003 Server in
a new Domain, creating all the Groups and Policies and testing prior to the
upgrade. The existing DC was then demoted and joined to the new Domain and
all the roles transferred to it. Then the temp server was removed from the
Domain.

The Domain name was changed during the upgrade so all the workstations had
to be removed and rejoined to the new Domain.

All this worked pretty much as planned, but now they have a problem with a
number of workstations in that they can't delete printers, no matter what
user is logged it including the Domain Admin. The error message is "Operation
cancelled due to restrictions in effect on this computer, contact your system
administrator".

I've checked the GPO's and ran GPresult. There are no restrictions coming
from GPO's. The domain admin can make any change you want to permissions or
settings on the printers, but can not delete.

I suspect a registry setting, but I would like to know exactly what would
have caused this issue, how to correct and prevent it in the future.

If anyone has run into this please let me know.

Thanks