Whilst I did not have any set datefirst statements in my SP, adding it got the SP to work.

Funny thing, the SP had been working for six weeks on 25+ different servers (2005 to 2012); then, all of a sudden, this weekend it fails with the error:

Could not complete cursor operation because the set options have changed since the cursor was declared.

It's even stanger since I only use the reserved word set to set variables, so adding a set datefirst 7 makes no sense whatsoever, but it works