Although the specifics are probably not worth it now, as you've already moved to a different database, you should _always_ look into tuning your database if you have queries that seem like they're running a bit long.

I don't know enough about your database, so I don't know exactly what might've been going wrong, but I'd probably look at the following:

• Check which indexes are / aren't being used. (in mysql and postgres, 'EXPLAIN', in Oracle, 'EXPLAIN PLAN'). For a limited type of queries it can be more efficient to do a full table scan (but not when you're doing a count(*)).
• Have the database analyze the tables to decide when it should / shouldn't use indexes. (in mysql, 'ANALYZE TABLE', in postgres, 'ANALYZE', in Oracle, 'ANALYZE TABLE' and if your keys aren't evenly distributed, use 'dbms_stats.gather_table_stats')
• Check to make sure that you have enough memory allocated to the program to keep the necessary indexes pinned in memory and reduce disk IO.
• Reduce / eliminate the complexity of table joins if possible. (or force a specific type of table join as appropriate for the situation)