shardCollection fails with "couldn't find valid index for shard key" despite index existing

I'm attempting to shard a number of existing collections. They were all created and populated in a standalone mongod which has now been converted to a sharded cluster. Some of the collections have sharded successfully, others have failed with the above error. A possible cause of this was that the indexes were in the process of being created (with the background: true option) when the shardCollection command was first run, due to the script used not waiting for the background creation to complete.

Full example error: