ISSUE:
Domain member running Windows 2003 Server was upgraded to SP2 after which it started experiencing network errors, indicating bad machine account.
In an attempt to resolve the problem, the server was removed from the domain, but in the process of adding it back into the domain it failed with error "network path not found". Same error showed up when an attempt was made to connect from this server to shares on other domain servers.