I cannot add a network printer to workstation when trying to add it from the
AD directory, but the same printer can be added with the share name
(\\server\printer).

The printer is shared, and listed in the AD directory, but trying to add it,
or even right click -> Properties gives the "Could not..." error message.
This has nothing to do with user rights, since even Enterprise Admins get
the same error message.

If I add it "the old NT way" using server name and shared printer name, the
printer works fine.

Server = Win2003 SP1
Clients = Win2000 SP4

Printer = any (mostly HP printers)

Any ideas?

Your situation might be caused by a "ghost AD printer object". i.e. the AD
printer object is incorrectly invalid as a result of the print spooler
failing to properly update/publish the AD printer object.

More: The printer AD object is a child object of the server object. To see
child printer objects, run dsa.msc, enable the view, "User, Groups and
Computers as containers", click down to open the relevant server object.

Suggested solution: Delete the printer object using dsa.msc. Re-publish the
printer object at the printer queue tab page by unclicking, apply, clicking,
apply the "List in the directory" option. Restarting the spooler service also
causes a republish ... but for all printer queues set up in this way on the
spooler.