Network Browse for 2003 server fails

I have recently upgraded the PDC in the network to a 2003 server from NT4. When I do a NET VIEW or try to browse the network the new server is not shown. If I call it by name (\\server) I can see the shares.
I had originally thought it may be part of 2003 security, but I have now installed a 2003 terminal server and it broadcasts OK.
I have checked all the obvious (Domain controller security policies, SMB signing, File & print sharing) and can not see why it wont show up.

Any suggestions?