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?