I found the solution.  What you need to do is:

1. Create a new XhtmlString
2. Loop through the old XhtmlString's fragments, and append each fragment to the new XhtmlString.  Skip the one you are trying to manipulate and inject a different fragment instead.
3. Save the IContent housing the XhtmlString

So in my case, the first fragment was static HTML and had a typo in it.  We needed to find this and fix it, so the pseudo-algorithm looked like this:

var clone = myBlock.CreateWritableClone () as MyBlock;
if (clone != null && clone.MainBody != null && clone.MainBody.Fragments.Any ()) {

    // replace first fragment with new bit of HTML:
    var targetVal = "<h1>Hello World</h1>";
    var newXhtmlStringValue = new XhtmlString ();
    newXhtmlStringValue.Fragments.Add (new StaticFragment (targetVal));;

    // skip first fragment and add the rest to the new xhtml string
    clone.MainBody.Fragments.RemoveAt (0); // purge first item from old body
    foreach (var fragment in clone.MainBody.Fragments) {
        newXhtmlStringValue.Fragments.Add (fragment);
    }

    // set the main body over to the new xhtml string
    clone.MainBody = newXhtmlStringValue;

    // save
    _contentRepository.Save ((IContent) clone, SaveAction.Publish, AccessLevel.NoAccess);
}

My initial suggestion would be something like this:

var clone = myBlock.CreateWritableClone () as MyBlock;
if (clone != null && clone.MainBody != null) 
{
    var oldText = clone.MainBody.ToInternalString();
    var newText = oldtext.Replace("old", "new");
    clone.MainBody = new XhtmlString(newText);
    _contentRepository.Save ((IContent) clone, SaveAction.Publish, AccessLevel.NoAccess);
}

But your approach looks safer. Maybe I will mess up blocks, personalization or some other stuff I did not think of?

Correct Tomas, converting the entire XhtmlString to an internal string, and then parsing it back will break any dynamic fragments inside (personalized, blocks, etc).  This could possibly be a bug on the XhtmlString constructor.  I couldn't find any other way around this except to copy the fragments out one by one and inject a new static fragment in the target location.