Ok, I found a temporary solution, but it will only work for phones with SD cards.
I used to store my offline maps on the internal memory of my phone. I then used the app Lumia storage check BETA to change the default storage location for offline maps to the SD card. Then, voila, all map app were now working again. But it was necessary to download maps again as these apps are now trying tho read maps from the SD card. It needs to be the beta as the non-beta does not have the option to change this setting.
This solution is temporary because:
Problem 1: if I switch back the default location of offline maps storage, the apps will read the data stored on the phone, which is broken, and the problem will return.
Problem 2: after switching the storage location to the SD there will be no way of deleting maps stored on the internal memory of the phone (none that I know) unless this setting is turned back to default. If there is a way to delete these maps and download them again the problem will be solved...