Could be fragmentation, could be out of date statistics. There are reasons for SQL not to use an index that looks perfect.
Edit: Sounds like it could also be parameter sniffing.
Could you post the proc, the table design and the indexes that you have on it if you want suggestions on it?
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability