Have you tuning your database as detailed in the Performance Tuning Virtuoso for RDF Queries and Other Use post ?
What does the output of running the status(); command from the Virtuoso isql command line tool report as the status of the database when running typical query workload.