Device name on router is different than OS X hostname
There are three different hostnames that macOS/OS X uses:


ComputerName
HostName
LocalHostName


Each of these values can be found in /Library/Preferences/SystemConfiguration/preferences.plist



ComputerName

scutil --get ComputerName


This is Apple "friendly" name for the computer and can be found in System Preferences >> Sharing >> Computer Name.  According to the man page for scutil, it is described as "The user-friendly name for the system."

According to Apple, the ComputerName is The AppleTalk name and the default name used for SLP/DA1.  It's a zero-configuraiton protocol that allows you to set up a simple network without a DNS/DHCP server but allow you to reach the different resources via a host name.

HostName

scutil --get HostName


According to the scutil man page, the HostName is "the name associated with hostname(1) and gethostname(3)". This name can come from any of the following sources:  


The name provided by the DHCP or BootP server for the primary IP address
The first name returned by a reverse DNS (address-to-name) query for the primary IP address
The local hostname
The name “localhost”


(In my virgin install of El Capitan, the HostName defaulted to LocalHostName)

LocalHostName

scutil --get LocalHostName


This is for Bonjour2 services on the LAN.  This is how, on a small LAN without DNS/DHCP, Apple computers can discover and interact with resources such as file sharing on other machines, printers, etc.  This name gets set when you initially configure your Mac.

TL;DR

It is using "the first name you ever set" because during initial setup, it set the LocalHostName which it assumed would forever be.  When you re-configured using the GUI, you changed the ComputerName which did not modify the LocalHostName.

If you wish to fix this in your router, simply set your LocalHostName using the command:

scutil --set LocalHostName MyNewComputerName.domain



1 SLP/DA Service Location Protocol/Directory Agent. The Service Location Protocol is a service discovery protocol that allows computers and other devices to find services in a local area network without prior configuration.

2 Bonjour is Apple's implementation of zero-configuration networking, a group of technologies that includes service discovery, address assignment, and hostname resolution.