Yeah, seen that, 15 minutes definitely rings a bell.
You don't give us much in the way of clues, such as the operating systems in use?
If it's an ill-assorted mixture of Windows versions one approach is to wait two or three minutes rather than 15, then on "hismachine" try to navigate to "hermachine" by typing "
\\hermachine" in the Run dialog rather than trying to refresh "My Network Places". (If this works then you can of course set up a shortcut for next time.)
(On seriously old mixtures of versions of Windows - we're talking networks mixing WfW3.11 and NT3.5 here, that sort of thing - you have to fiddle around with settings for master browsers, but that was decades ago now.)