I run complex table stuff on Linux with FOP pretty consistently, and have not experienced the slow-downs you mention. Are you running under Linux with a decent amount of memory?
I have performance problems with Fop on Linux for S390. The same document (for example 4 tables on one page) takes 3 seconds on Win NT, while it takes more than one minute on Linux. The same happens with examples which came with FOP - they are slow on Linux. What should I do?