Can't see or browse SMB file shares depending on the router

Question

TL;DR Version

I can't browse the SMB shares on my fileserver from some of my devices; if I use a new router it works. FIX IT FIX IT FIX IT!

The setup

I have two routers, a D-Link DSL 2370R and a Technicolor TD5130v2. I have an Ubuntu file server running samba (I use webmin to manage it), and the following devices that I connect to it.

• My media center, a Raspberry Pi Model B running OpenELEC
• A laptop running Ubuntu 12.04.2
• A laptop running Windows 7 Starter 32 bits
• An android 4.4.2 Kit-Kat powered Moto G, running the LAN Shares module of the ES Explorer App

The Pi and the file server are using wired connections, all the rest use wi-fi.

I want to be able to see the file server and talk to it from any device, but I'm having visibility issues when I use the Technicolor router. (I could just use the D-LINK router and ditch the other one, but I'm having a hard time configuring the internet connection on it; besides, the Technicolor router has a stronger wifi signal.)

First Scenario

If I connect all the devices to the D-Link router:

1. The "Networks" entry on Nautilus won't show all devices, but on the "Workgroup" group under the "Windows networks" item, I can see and browse the file server, the 2 laptops and the media center.
2. If I insert the IP addresses of the devices on Nautilus (smb://IP), or its names (smb://devicename), I can see and browse them.
3. Win7 won't show any device on the network folder, but if I type "\IP" on Windows Explorer, I can browse all files
4. Performing a network scan on the android app, it will show a list of every device identified by its IP; all are browseable.
5. OpenELEC smb browser will show all the devices (including the Win7 laptop) on the WORKGROUP group, all are browseable
6. Performing the smbtree on the Ubuntu laptop will show all the devices and all the shares for each device.
7. Here's the output of the smbclient command on the Ubuntu laptop for itself, for the fileserver, for the Win7 laptop and for the media center.

Second Scenario

If I connect all the devices to the Technicolor router:

1. No devices show on Nautilus' Network section. Clicking the "Workgroup" item pops up an error alert ("Failed to retrieve the shares list from the server", or something like that, not in English).
2. If I insert the IP addresses of the devices on Nautilus (smb://IP), I can see the devices, but inserting the names (smb://devicename) issues a similar error.
3. Win7 won't show any device on the network folder, but if I type "\IP" on Windows Explorer, I can browse all files
4. Performing a network scan on the android app, it will show a list of every device identified by its IP; all are browseable.
5. OpenELEC smb browser will show all the devices (including the Win7 laptop) on the WORKGROUP group, all are browseable.
6. Performing the smbtree on the Ubuntu laptop will show all the devices, but no shares for any device except the localhost.
7. Here's the output of the smbclient command on the Ubuntu laptop for itself, for the fileserver, for the Win7 laptop and for the media center.

Solution

I've found out if I either

(1) disable the DNS Relay option on the "Local Network" tab and manually set valid DNS servers such as Google's 8.8.8.8 and 8.8.4.4

DNS Relay means in this case that all your machines send their DNS queries to the relay. The relay sends the queries to the DNS server of the provider or whatever is set in the router's WAN settings.

When it receives the answer it sends it back to the machines and stores it for a short time. So if another machine in your network searches for the same address, it will receive the answer directly from your router without asking internet servers again. (So there is a little memory which remembers the queries - so called: DNS cache)

or

(2) Keep DNS relay enable, but disable the "DNS" option on the "PPPoE" section of the "Internet Setup" tab, and manually set and manually set valid DNS servers such as Google's 8.8.8.8 and 8.8.4.4

then it will work.

This answer takes care of the "how to fix it", but I have absolutely no idea of what is going on.