The issue appeared to be in my network. For some reason, my phone automatically downloaded a wrong proxy IP adress and a port number for internet settings. This caused an error when downloading files of 5+MB.
I contacted the operator and the next day they explained how I should reconfigure the phone. Worked like a charm.
Another thing, from home, settings->applications->manage applications. Find the Google Play Store, tap it, and tap the button "uninstall updates". The first time that you run the store, it may update to the new store again. It may be that the last update installed incorrectly.
