Personal Hotspot not working with my MacBook Air

Hi Community

So I have an iPhone 6 and a MacBook Air (Mid2013), who both meet the requirements for the new personal Hotspot in iOS8.

I connected the 2 devices and it worked for some time. I could activate the personal hotspot without even touching the phone. I was very happy, but suddenly it stopped working, although I didn't install a new update on any of the two devices (both are still up to date). At some point, I had to turn the hotspot on manually to get it working, but now, the only way to connect to my hotspot, is to start diagnostics and connect trough that window.

The bluetooth connection works without a problem& my iPhone hotspot works perfectly with my iPad 3.

I tried everything, someone wrote on a website that the iCloud might me the problem, so I disconnected both devices from iCloud and reconnected afterwards. It worked exactly once after that. Then, my MacBook kept saying that the personal hotspot could not be activated (even if I activated the hotspot manually).

Thanks for every kind of help, I'm super frustrated 😟