Forgot to add, the permission are 755 for the albums and 777 for the cache. Each image is quite small, under 7kb. I've sucessfully managed to add files bigger than 1mb and they're loading just fine so I don't what could it possibly be.
Btw, tried the &debug trick with a couple of other images and I got the same error message even though they're loading correctly...

It is really not the file size of the image that matters, it is the dimensions of the image. Look at the troubleshooting guide for information on how much memory various dimensioned images require to process.

If some images are working for you and others are not it is almost assured that you are having memory limitation problems.

Turns out it's not a memory limitation problem. I installed a fresh copy of zenphoto to a new directory yesterday, uploaded all the pics that refused to show up in the other gallery and everything was working fine.
Do you have any idea what else may be causing this problem?

You would have to find your CGI log and see what errors were reported. Also check the individuial files and see what their permissions are. Just because the folder has the right permission does not mean the individual files do.

Where can i find the CGI Log`?

On your server. If you don't find it ask your host.