I'm using Zonealarm as well and it works (with Gnotella, I guess also with other clients?). I can connect to others, others can connect with me, up- and downloading works fine - I can even download from firewalled (by hardware!) comps making push requests. It is necessary (at least for others to connect to you) to "allow server" for gnotella in zonealarm.
As you said it wouldn't work without zonealarm, I guess your problem is somewhere else - but now you know for sure (computers and "for sure"? ) that zonealarm is not the cause.