Msngr on LAN works from 98 but not XP

I have just added a new XP machine to the office network,
but I cannot get Messenger, MSN or Windows, to connect. I
have gone through the troubleshooter, checked all the
help options.

Tried opening port 1863 on the proxy server (running SBS
4.5 with proxy server 2 - but didn't even need to add
these settings on the 98 options). Also tried all combos
of proxy server settings in Messenger that I can think of.

Error shown is 0x8100035b.

Advice most appreciated.