Well since we can't recreate this and it seems to be an isolated problem, the best way for you to fix it is probably to turn on Output Buffering in PHP if you can.... it would fix the problem entirely.
With me, using Apache, PHP4 with Output Buffering turned [i]off[/i] (the only way this problem can possibly appear), mod_rewrite off, etc etc. everything works perfectly.
And Daniel, since you say "zenphoto is my new hobby", want to help us out and become a dev? ;-)