I don't know why it does this, but I have similar troubles. I use

kdeconnect-cli --refresh

instead of rebooting though.

Had similar issues, disconnecting wifi and reconnecting it on the computer usually fixes it.

It's been happening on the latest macOS as well. I just quit and relaunch the app to fix it; but yeah, it's annoying.

I managed to fix the same problem by installing avahi and nss-mdns.

sudo apt install -y avahi-daemon avahi-utils libnss-mdns

Should do the trick on Ubuntu.

I think I just had the same issue, but not with sleep, I logged out and back in