(Longshot guess, but I've been burned by this in the past too)

Have you tried connecting via a numeric IP address ? Windows has been known to have some nasty resolver caching behaviors which, if not registry hacked properly, can cause it to hang onto a bad DNS resolution for a long time...so if your target has changed its IP address recently, the Windows resolver cache may not have flushed yet.

Here's the story wrt WinXP...