Using a 10-shard cluster all running on the same host (same setup I posted to mongodb-dev for 1.5.6, http://s3.amazonaws.com/dotclue.org/shardtest-1.5.6.tgz), the first query in a new connection always fails with the same error:

% mongo jmdict
MongoDB shell version: 1.5.8
connecting to: jmdict
> db.dict.find(

{"r_ele.reb":"???"}

)
error:

{ "$err" : "too many attempts to update config, failing", "code" : 10195 }

The log file for the mongos I'm connecting to shows the following for each failure:

Tue Aug 3 13:06:20 [conn10] ns: jmdict.dict ClusteredCursor::query ShardConnection had to change attempt: 0
Tue Aug 3 13:06:20 [conn10] ns: jmdict.dict ClusteredCursor::query ShardConnection had to change attempt: 1
Tue Aug 3 13:06:21 [conn10] ns: jmdict.dict ClusteredCursor::query ShardConnection had to change attempt: 2
Tue Aug 3 13:06:23 [conn10] ns: jmdict.dict ClusteredCursor::query ShardConnection had to change attempt: 3
Tue Aug 3 13:06:26 [conn10] ns: jmdict.dict ClusteredCursor::query ShardConnection had to change attempt: 4
Tue Aug 3 13:06:30 [conn10] ns: jmdict.dict ClusteredCursor::query ShardConnection had to change attempt: 5
Tue Aug 3 13:06:30 [conn10] UserException: too many attempts to update config, failing

If I run db.dict.count() before the query, it succeeds every time:

% mongo jmdict
MongoDB shell version: 1.5.8
connecting to: jmdict
> db.dict.count()
877887
> db.dict.find(

{"r_ele.reb":"???"}

)
{ "_id" : ObjectId("4c5871618fcf08e654dc3f04"), "trans" : [

{ "trans_det" : [ "Anata" ], "name_type" : [ "surname" ] }

], "k_ele" : [

{ "keb" : "?" }

], "r_ele" : [

{ "reb" : "???" }

], "type" : "name", "sense" : [ ] }
...