Issues connecting to Samba share via netbios name

I was wondering if anybody have experience anything similar to the following:

I got a Linux server, creatively named "Server". I run Samba on it, and for yours, things have been smooth sailing. Until recently, where it developed an odd problem.

The server shows up in my locations in finder, or when I browse the network, as "SERVER". Now, a few weeks ago, things started getting odd. My Time Machine began to fail, and I couldn't connect to SERVER via finder. When I clicked SERVER in finder, it says "connecting" for a while, and ultimately fails. Oddly, If I attempt to "Connect as" to server, via finder, it never gives me the dialog to change username/password.

Now, if I goto "Connect to server" in finder, and try and connect to smb://server.local, I can connect. After changing Time Machine to use server.local, it is working again.

But, it doesn't auto discover server.local. I need to manually connect every time, and the, seemingly broken, SERVER entry is what I always see both "Network" and as my default server under locations.

[Edited by Moderator]