I had to restore 16.04.0 and wanted to try again. I updated OTA, but got caught in a loop initialising apps. I found a way out, thanks to @maba007 and @Spielmops
- Updated OTA to 16.05.0 and let initialise all apps for first time
- Interrupted the second initialisation process by launching TWRP (pressing Off button + Volume up for some time)
- Wiped Dalvik Cache and Cache
- Flashed the Xposed Framework (as I had it already installed and it was deactivated by update)
- Downloaded latest OpenGAPPS installer, transferred it to phone and flashed it.
- Wiped Dalvik Cache and Cache again
- Rebooted System
Half the icons and widgets disappeared from the Home screen, but they all worked fine and all the data was still there as well.
And now the GPS works just great again, system runs smooth and the phone knows where I am!
Edit and PS: Huge thanks also to @jochensp, as it seems that the GPS fix in the last update is thanks to him! Cheers pal!