Change arduino.local server address
That should be working fine.

I just logged into my Yún and changed its name by editing that file.  I then restarted avahi-daemon since that is what broadcasts its name (faster to restart the daemon that reboot the whole Yún).

Browsing to the new name worked fine.

matt@dell:~$ ssh root@arduino.local
root@Arduino:~# vi /etc/config/system
(edit the config file)
root@Arduino:~# hostname skybridge
(manually changing the hostname so I don't have to reboot)
root@skybridge:~# /etc/init.d/avahi-daemon restart
(restart the avahi daemon)


Browsing to skybridge.local now shows me the Arduino login as it should.

As a further test I have just rebooted my Yún so it runs everything from scratch and it still works fine.

There are a number of caches involved in the system, any of which may be getting in the way.  It could be that the browser has cached incorrect or out of date information about the FQDN (fully qualified domain name) for the name you have given your Yún, in which case just closing and re-opening your browser may help.  It may be that the mDNS lookup system on your computer (you haven't mentioned which operating system you are using, which is a big factor) has cached old or out-dated information for the FQDN, in which case flushing that cache may help (how you do that depends on your OS), or just rebooting your computer.

Incidentally, if you are on Linux (Windows lacks these basic networking facilities along with many other basic tools), you can query the network for your Arduino Yún with the avahi-browse and avahi-resolve commands.  OS X has similar tools, but I don't know off hand what the commands are:

matt@dell:~$ avahi-browse _arduino._tcp
+  wlan0 IPv4 skybridge                                     _arduino._tcp        local
^CGot SIGINT, quitting.
matt@dell:~$ avahi-resolve -n skybridge.local
skybridge.local 192.168.0.252