Here's my setup...
My network consists of a TC (ac, only a few months old) using both 2.4 and 5GHz channels with the same name, and an AirPort Express (n) extending the network. My 2013 13" MacBook Air (1.7 GHz i7) has never exhibited the problem, nor has my wife's late-2008 MBP. My mid-2011 27" (3.1 GHz i5) iMac has been the only problem machine. I did a clean install on both the MBA and the iMac, and just upgraded my wife's MBP. All machines are on wireless.
If memory serves, these are the steps I followed: (1) Disabled all sharing preferences along with "Wake for network access." (2) Restarted the TC (I don't believe I've ever disabled BTMM in the TC settings). (3) While the TC was restarting, I quickly renamed the iMac to its original name and rebooted. I've also resisted the urge to enable any of the sharing preferences on any machine. It's been almost a week and so far, so good. But as others have had the issue reoccur after following a similar procedure, I'm awaiting the same fate. At which point I'll resemble the bishop from Caddy Shack as I bellow, "Rat farts!"
I should also note that my TC has been flaky since upgrading to Yosemite (the MBA's AirPort Utility won't see it and I'm mostly unable to connect to it when I select it under Shared in the Finder). But I believe someone else here reported having the same renaming problem using a different router. Hope this helps as we try to pinpoint the problem. My money's on Bonjour, but what do I know.