I have this same problem, and I'm *REALLY* unhappy about it. Handoff worked fine with iOS 8.0.2 and suddenly today after I upgrade to iOS 8.1 the options vanishes from my iPhone and my Mac (in FaceTime).
I've double-checked my Apple ID logon to iCloud on both Mac and iPhone .. doesn't work. I also lost handoff for calls on my iPad, so I suspect the problem is the iPhone and not the Mac/iPad (which also makes sense since this was the device that got the software upgrade).
Overall, with broken Bluetooth, broken iCloud, broken Handoff and numerous tinkering needed before these things can work, this is a VERY pop user experience from my perspective. What happened to the "it just works" Apple of old? As several commentators have noted, Apple quality has really gone downhill with iOS 8 release.
So, I have a clean Mac with OS X Yosemite, an iPhone with iOS 8.1, a clean WiFi network with everything working ... and NO cellular handoff, or even visible options. And yes, other Handoff stuff like SMS messages on my Mac works just fine.
Does anyone have any other ideas of things to try or trouble-shoot?
UPDATE: I worked on this some more, and DID fix it, as follows:
1. Sign OUT from iCloud on iPhone.
2. Sign IN to iCloud on iPhone
3. Wait 5 minutes
4. Check in Settings on iPhone for Cellular Calls option .. enable if not enabled
5. In FaceTime on Mac, check that iPhone Cellular Calls option is now visible and checked.
6. Repeat on iPad etc
The "master switch" here seems to be the sign out/sign in on iCloud on the iPhone. Apparently during the iOS 8.1 upgrade iCloud "forgot" my phones capabilities, and only re-discovered them during a NEW sign-on from iCloud. Once that was done, the other devices all enabled automatically. HTH.
--Tim