There must be something flaky in your Linux install, JDK, FOP setup, or xsl formatting. Hard to tell without looking at all the particulars of your box and project.
I’ve used FOP on a few Windows boxes, and several Linux servers, and it’s always faster under Linux for me. I’d start by taking a hard look at your xsl, and work out from there. Wish I could be of more help.
Our Linux has 0.5Gb memory. I am trying to make pdf from file headfoot.fo, which came with examples in Fop 0.20.1. It takes about 13500 ms per page while in Win2000 it takes 350 ms per page. Why such diference?