So... after you added the index, did you get index seeks or just scans? Also, never trust the execution plan by itself... did you turn statistics on or run profiler against the query before and after? If not, you have no concrete proof that adding the index actually helped overall performance or not.
--Jeff Moden
Change is inevitable... Change for the better is not.