MS SQL 6.5 - How to improve speed??

I am using MS SQL 6.5 and my application is using ODBC to access the
database via ODBCExpress. When we had about 5 users logged in and using the
application, my application used to fly around wonderfully. Now that we
hooked up the other department to the server using the same application,
bringing the total users to about 12, querying the database has slowed down
tremendously. What can I do to improve the speed? I have increased the total
user connections to about 100 on the MS SQL configuration.

Any help is greatly appreciated.

Regards
Andrew
Minds At Work Corporation