Have you created actual CollisionPolygons for the walls and floor collisions, or are you doing collide-with-geometry? Collide-with-geometry is way, way, slow, of course.
The call:
base.cTrav.showCollisions(render)
will light up collision polygons as they are being tested. If you see a lot of polygons lighting up, your scene is poorly structured.
You can run PStats to prove the problem is in the collision system and not somewhere else.
David