SQL 2005- stored procedure performance troubleshooting
Things like select count(*) are just fine as long as the where clause is indexed correctly.

DTA may or may not be of any use.

The actual and estimated plan are what you need to look at.  It'll tell you if there are any indexes which are missing.  The indexes which are used will be in the execution plan.