Network Discovery stopped working on Samba network

I am a software developer trying to help with a network issue (letting you know I don't know what I am doing). We are a very small shop.

We have a Samba network with a dozen or so Linux servers, and maybe 2 dozen users. Network discovery stopped working last week. Users cannot browse to network resources. Most users are Windows 7, I have an Ubuntu box and a Fedora box with the same issue.

I can connect by manually entering resource locations (by name). Windows users can as well, but have to manually connect by IP address.

There have been no intentional changes to the network. We did have a power interruption last week. We have rebooted the router, and the switches.

Can anyone give me some guidance? Thanks for any help you can offer.

EDIT:

We still have this issue. We have one Mac user - Network Discovery works for him.