Was the time/clock of the computer in sync with the servers/computers on the network?

I think due to encrypted connections if the difference of time is significant you can't connect or see shares, recently I couldn't join a samba server to an active directory with a 2003 server because of 10 minute difference of the clocks. And when I did sync the clocks between the 2003 server and the samba server, a windows XP PC which had it's clock out of sync couldn't see the shares on the samba server until I corrected it's time also.

You did mention early that the timezone was initial wrong...