600 quads seems like a bit much considering your game. Are you sure culling is working? Did you consider using a library which does culling for you (Xith3D, jME, Java3D)?
What are your system specs? On my (not so new) machine, I easily get 60fps with your game.
Did you check if fill-rate is your problem? (If so, you could try to render front-to-back).
Did you profile your code?
I think that I don't need an other library, JOGL does the last part of the culling and my algorithm gives it less data to allow the GPU to do something else.
Mandriva Linux 2007, AMD Sempron 2300+, 2 GB DDRAM 400 Mhz, ATI Radeon 9250 Pro with a very bad Xorg open source driver (my former girkfriend has better performance with a SIS 661 FX chipset under Windows XP with a proprietary driver

).
I use backface culling through JOGL.
Profile? A liitle bit and I think I have found the main problem. Display lists are quicker than static VBO only if you handle very small pieces of data.
I'm stupid, I have split all the walls into very small pieces to implement a temporary voxel-based visibility culling and my culling compensates my stupidity of splitting all. My culling is excellent but my structures are not correctly designed, I will correct it. I use 4 textures. I think that I will regroup all the walls of a same "cell" in a SINGLE vertex set (a vertex set might use VBO if available).