Weird permissions problems for sites/default/files
I managed to figure this out with the help of the company providing the hosting. So, I'm sharing the solution, in case others have similar issues.

The solution is to make PHP run as a "FastCGI application", instead of an "Apache module". This way, Drupal uses the same user I use to upload files via FTP, when it creates files, etc.

The new website worked fine because I used the one-click installer offered by the hosting provider, which ran everything using the apache user. The old website did not do this.

This solution &amp; problem should apply to all hosting providers using Plesk.