How can I speed up a stored procedure?
Amazingly broad question but a couple of simple answers.  


Indexing like you suggested.  Make sure the appropriate indexes exist and if the need is great enough make sure they are all covering.
Get rid of the *.  Specify the columns you need.  If you are pulling across 100 columns over a million rows that's going to be a LOT of data.  If you only need 3 columns only specify 3 columns.
Change the timeout.  This sounds hokey but honestly sometimes it really is the answer.  SQL Server (for example) doesn't actually have a timeout so the problem is on the connection side.  Have them increase the timeout to 30 seconds (assuming this is an acceptable amount of time, and it frequently won't be).
Make sure it's the DBMS's fault.  It's very possible you are having a problem on the connection side that's causing it to take 5-10 seconds just to connect.  Fix that and you are well within your time.