Eu tenho problema similar quando minha placa de rede do windows 7 foi configurada para ter dois ip's 192.168.1.xe 192.168.0.x. Meus computadores do grupo de trabalho funcionam no x.x.1.x. Depois de eu ter excluído o ip x.x.0.x do seccound, o win 7 encontrou o pc do grupo de trabalho e se conectou a ele pelo nome. (conectando por ip foi capaz o tempo todo)
É estranho porque no mesmo grupo de trabalho eu tenho win xp com dois ip's: 192.168.1.xe 192.168.0.x. e seu trabalho sem nenhum problema.