I have read this thread, after a few hours of searching, lurking and looking through the forum to find a solution to my problem: http://www.zenphoto.org/support/topic.php?id=975&replies=6#post-5314

And in that thread this is mentioned:
" It's probably the php 'memory_limit' value -- this is different from the 'max_upload_size' and controls much of what zenphoto can do. Try setting it to 64M or higher."

Now where do I go about and change this ?

My dilemma is that there is infact a restriction (in some odd way, might not be in ZP, but there is...), either in size (px) or size (mb) as I can't upload files that is over 1400x size (this one can however weigh 2568Kb) to compare to the one that is 1600x (and weigh 2739Kb)

Sorry, I didn't see this post earlier. You can only change the 'memory_limit' value if you have access to your php.ini file. If not, you can always ask your host to increase it for you.