This problem was already found and described at http://groups.google.com/group/mongodb-user/browse_thread/thread/dddeeb7be75a944a. To recap – adding a file to a newly created GridFS database that is hosted in a replica set, when slaveOk is set to true, leads to a "Command 'filemd5' failed: exception: best guess plan requested, but scan and order required" error.
The problem is that indexes are not created for a new database, since the check in MongoGridFS.EnsureIndexes(int) prohibits index creation for slaveOk connections.
I concluded a patch (will attach it later) that fixes the problem. Please take note that it does it in a bit indirect way – I thought that introducing some kind of "ignoreSlaveOk" parameter to MognoGridFS.EnsureIndex methods wouldn't be any good, so I just check the request nesting level (GridFS writes are done within nested requests so it's a fine indicator).