does the table have a clustered index?

you cannot do a covering index as the limit is 16 columns, I would deffinitally add a clustered and re-create a non clustered on time.