In my case, it was solved by raising the memory limit in the server.
@Vayu, have you checked with a phpinfo(), that you are actually running 256mb? If so, and just for testing, try raising the limit and see if that helps. It might be that it is a memory problem.
Good luck!