I also tried an old Linksys ADSL router which was previously reliable, but found no improvement.
I can access shares on an Ubuntu 16.04 server from an Ubuntu 16.04 or Debian client only if ufw is deactivated on the client machine, which suggests to me that perhaps ufw or smbclient is at fault. If ufw is on,
$ smbtree -d6
says it can't find the master browser for WORKGROUP, despite ufw allow in samba being set on the server. I've tried ufw reset on both. I've also tried installing cifs-utils.
I wonder if smbclient's outgoing traffic isn't being correctly marked as established to prevent blocking of the server's replies to dynamic ports, which is what seems to be happening, although there's nothing more descriptive that I can see in the client's logs.
I'm not sure a) whether a software or a router problem is to blame, or b) how to go about more advanced debugging.