Ok, I managed to make it work now. I am not sure how, though. I did some small changes to the app, stepped the version number and distributed that in the same way as before. Now it managed to install correctly.
One other thing that I did, is to remove the old app completely from the phone before doing the new install. I did not manage to do that before, it always remained on the phone with its icon in half-loaded state. Now I did a combination of Remove from iTunes and clicking the 'x' delete icon multiple times, and it finally disappeared completely.