Yes, it's obvious the query time improves, now that you have a nonclustered index that is twice as small as your Clustered index. It would be even better if you used "EntityIdentifierSequence" as the nonclustered, since it's also twice as small as your new nonclustered index.

Now that you get a real good time running this query, that is because the query is cached in the sql server, if you want to have a real portrait of the time the query will take on the first run, you should use this:

dbcc dropcleanbuffers;

dbcc freeproccache;

select Count(*) from TheTable;

It will give you the exact time the query will take on the first run, or when the results are not cached, and please post the .sqlplan for this (.sqlplan zipped, so we get a graphical view), I'm sorry to ask again, but I'm really curious to see what could be the issue on this, going from 9 scans, to 1.. that is weird in my book!

Thanks,