Might be a database issue, especially if your database isn't on the same server as your Drupal/Ubercart installation. (A lot of web hosts use a shared database server, so even if you're on a "semi-private" you may be greatly affected by other database users and bandwidth.) You can use phpMyAdmin to look at performance, you can install the devel module (http://drupal.org/project/devel) and see what it says about your query times. Try this utility to analyze and fix performance issues: http://highervisibilitywebsites.com/tuning-primer.sh.zip