Ok, so the problem here was that somehow my iPhone was connected to iCloud... But it wasn't at the same time... This is really weird, and Apple should at least notify on this somehow, because my iPhone was connected to iCloud and synced. Wow.
Worked the same for me, though also required e) after a) to d):
a) going to the apple discussions (as mentioned) to 'register' my device(s) with my apple id. (weird)
b) turning iMessages off and on (on both devices)
c) turning my icloud off and on (on both devices) (scary dialog boxes, push on)
d) turning by bluetooth off and on (on both devices)
and finally, after none of that worked,
e) turning both devices off and on.
Presto, it finally worked. The feature only seems to work if the email or message or calendar (whatever you want to hand-off) is actually open on the screen on one of the devices. Unlock other device and the email or messages or whatever icon appears bottom left. Swipe it up and roll.
I have had a few of these issues with icloud and apple id's. Seems like you really have to reset all icloud and messages services to get hand-off working properly.
Best Answer
Typically, resetting the network settings clears the network connection so that the keys Apple generates / matches to know which device is yours may be expired or need to be renewed / re-keyed.
Connect to WiFi on all devices and make sure iCloud is working would be my first triage step here.