Unable to connect to network share

On our company network there are a number of clients that are having problems connecting to the company file server (Windows Server 2003 R2 Enterprise x86).
The share are mapped to a drive letter on the client. The drives are showing up with a red X and can't be opened.

Most people can access the network shares ok.

I have an idea that the workstation service is at fault.
The output of net config workstation on a faulty computer is

C:\>net config workstation
Computer name                        \\vistacomputer
Full Computer name                   vistacomputer.xxxx.xxxx-xxxxxx.co.uk
User name                            username

Workstation active on 

Software version                     Windows Vista (TM) Business

Workstation domain                   xxxxxx
Workstation Domain DNS Name          xxxxxx.xxxx-xxxxxxxxx.co.uk
Logon domain                         xxxxxx

COM Open Timeout (sec)               0
COM Send Count (byte)                16
COM Send Timeout (msec)              250
The command completed successfully.

On a working computer it is

C:\>net config workstation
Computer name                        \\vistacomputerthatworks
Full Computer name                   vistacomputerthatworks.xxxx.xxxx-xxxxxx.co.uk
User name                            username

Workstation active on
     NetbiosSmb (000000000000)
     NetBT_Tcpip_{DABE06A7-5BF8-4ADF-B6C4-73EDB8D7971B} (00505694241B)

Software version                     Windows Vista (TM) Business

Workstation domain                   xxxxxx
Workstation Domain DNS Name          xxxxxx.xxxx-xxxxxxxxx.co.uk
Logon domain                         xxxxxx

COM Open Timeout (sec)               0
COM Send Count (byte)                16
COM Send Timeout (msec)              250
The command completed successfully.

Looks like the workstation service is disassociating itself from the network connections.

Any ideas?