Is there any performance hit involved in choosing gzip over deflate for http compression?

We recently switched some of our sites from deflate to gzip and noticed a significant increase in cpu load on our servers.

Is it possible that you are experiencing cache miss? That is, compressed content is sometimes cached compressed but switching compression schemes would (or at least should) invalidate that cache causing dramatically increased cpu utilization. Did you try switching it back?

gzip is, basically, deflate with some additional headers. So there should not be a significant performance hit. Now, maybe your deflate tool is just more efficient than your gzip tool. Are you using the same tool for both compressions or two different ones?