Be sure that all of your indexes are installed, and if SQL Server is not using the indexes properly, you may need to use an index hint. i.e...

select *...