The problem was that the plan was doing a table scan on the underlying table, and not using the indexes I had carefully crafted.
I had even created a second non-clustered index to try and make sure it was a proper covering index for the query.
Read on to see how Randolph solved the problem.