I am using 2.0 release of mongodb in a setup with 4 shards. I created a test collection with following data:
mongos> db.test1.find()
{ "_id" :

{ "a" : 1, "b" : 1 }

, "c" : 3 }
{ "_id" :

{ "a" : 1, "b" : 2 }

, "c" : 3 }
{ "_id" :

{ "a" : 1, "b" : 3 }

, "c" : 3 }
{ "_id" :

{ "a" : 1, "b" : 4 }

, "c" : 3 }

I sharded the collection with shard key: "_id" which worked fine. Even new inserts are working fine after sharding but "upserts" are not working.
For example , following command:
$collection->update(
array('_id' => array('a' => 1, 'b' => 3)),
array('c' => array('$inc' => 1)),
array('upsert' => true, 'safe' => true)
);

results in this error: ** EXCEPTION: can't upsert something without valid shard key

I am using PHP 1.2.3 extension to connect to mongodb.

Above error can be reproduced also when I use "_id.a" as a shard key rather than "_id".