Problems with any mac client seeing windows shares

Anybody had this? Everything has been running fine until last week. We are running 10.4 on all our clients, with our Windows servers running server 2003. While I was on holiday, the Windows team did a load of server updates which seem to have made all the macs unable to connect to most windows servers using SMB. I cant seem to find a pattern, but some servers work, but most dont. Its not the macs as I have tried rebuilding an emac with 10.4.2 and it still cant connect, and like I: say, it all worked fine until last week when I was on holiday, came back to find lots broken!