This is the long walkthrough on how to fix this problem which is due to the fact that a too low memory limit is set in the PHP ini file.
1.) The ini file can be in different locations depending on your configuration so start with uploading and running a script looking like this to the server:
2.) Run the script in the browser and locate the php.ini location, it could for instance be: /etc/php5/apache2
3.) SSH into the remote server or do whatever it is you need to do to be able to edit the file.
4.) Open the file in nano: sudo nano /etc/php5/apache2/php.ini
5.) Use CTRL-W to search for memory_limit.
5.) Change the value to more than you already have, I read somewhere that 64MB is good for WordPress for instance.
5.) CTRL-O (save) followed by CTRL-X (exit).
6.) sudo /etc/init.d/apache2 restart