Hey guys.. I was just about to give up on it too, specially when I found out it still wasn't fixed on its own when I updated to iOS 8.1. I don't ever post stuff but I thought it'd be best to let you guys know what I did as I FINALLY got it to work! Heres what I did:
Signed out of iCloud on my iPhone and Mac, then signed back in and when the prompts came up asking if I wanted to keep or delete the iCloud stuff on my phone I chose to keep them obviously.
Then on my Mac when I signed back in it also gave me a bunch of prompts to sync/merge contacts, mail etc. Make sure you set up Keychain as I somehow believe that played a big role in the fix, don't ask why but just do it haha.
Finally I switched off bluetooth on my iPhone and Mac, restarted the Mac and restarted my phone using the home button + lock button method (hold them both down for about 10 seconds or so). Note I restarted them at both the same time (somewhat) as I just had a superstition that'd make things work as I was desperate to try anything lol. Then I switched bluetooth on on both devices. Then I decided to send a photo from my mac to iPhone and vice versa using Airdrop to kind of force a connection between the 2. After that I used my iPhone as a personal hotspot for my mac to also force a connection (again, still desperate to try anything). Then I restarted both devices as I did before, and out of nowhere voila! The beautiful safari icon popped up on my dock when I opened safari on my iPhone, and the icon appeared on the lock screen when I used safari on my mac! I tried every app that I could think of that used continuity and they all worked!
But then a few hours later when I came back to my mac i noticed the app continuity only worked from my phone to mac but not the other way around even though I could still send SMS and calls through my mac. I tried restarting both devices but it still only worked from iPhone to mac 😟 so if anyone can find a fix to get back continuity back from my Mac to iPhone that'd be great 🙂
Hope this works for all of you! If it does please repost this to other forums you come across as Ive seen 10+ other forums regarding the same issue! Still a shame Apple had to make finding a fix (thats still buggy) THIS complicated! Not everyone has the time or patience to do what I just did! PLEASE FIX THIS PROPERLY APPLE!!!!