I've had this exact issue come up on deployments.

Drop FKs, drop Indexes, recreate FKs.

It makes sense that this would use the clustered index for the FK, though I can't say I put forth the effort into finding out why it was happening. Then again I wasn't awoken at 2am 😉