It is the clustering. I read the errror message a bit more closely. It actually says:

For non-clustered index the column could be an include column of the index,...

Thanks for comments, guys.

It really is that index causing the problem - I dropped it and the problem went away, then  manually recreated it, and the problem came back,...