Don!, I have spent many hours researching and struggling with this problem. There are lots of references to the problem on the Internet, but nobody has come up with a reliable solution, until now.
Magento uses an object model to handle all database I/O. This is supposed to insulate you from having to do tedious work, such as updating related fields. For example, if you add a new child category, the Magento object model will automatically update the 'children_count' in the parent record. The Magento object model basically lets you concern yourself with the data that you wish to write, while taking care of the housekeeping for you. However, when the object model does not do what it is supposed to, things really suck. That is the situation with the 'parent_id' field, and the 'path' field. Magento just does not update them the way it should.
The solution is to make the changes that you need to via the object model, save the object, and then FORCE the correct values for 'parent_id' and 'path' via a database query. I have found that the 'parent_id', and 'path' fields seem to be saved properly when the record is first created, but then they get messed up if the object is updated. This code presumes you are updating an existing category object.
$catId = 127; //ID of category record you wish to edit
$objCat = Mage::getModel('catalog/category')->load($catId);
if(!is_object($objCat)) {
throw new Exception("ERROR: Could not find category id: " .$catId);
}
//--- Make sure we have proper parent_id and path values
$parentId = $objCatParent->getId();
$path = $objCatParent->getPath() ."/" .$objCat->getId();
$objCatParent = $objCat->getParentCategory(); //We will need this parent category
$data = array('name' => 'My Cool Category',
'parent_id => $parentId,
'path' => $path;
$objCat->addData($data); //Use 'addData' rather than 'setData'
$objCat->save(); //Save to update record and break parent_id, path fields
//--- Now we get a connection to the database, build a query, and update record
$resource = Mage::getSingleton('core/resource');
$objCon = $resource->getConnection('core_write');
$tableName = "catalog_category_entity"; //Well, it's the name of the Category table
$query = "UPDATE {$table} SET parent_id = {$parentId}, path = '{$path}' "
. " WHERE entity_id = " .$catId;
$objCon->query($query); //Force proper values directly into table
Yes, yes, yes, you have to be very careful when you bypass the object model and make changes directly to database records. However, the Magento object model just does not seem to work here, so we have little choice. And since we are saving the record via the object's 'save()' method before it is doing whatever 'behind the scenes' work it is supposed to do. We are just correcting an error.
I hope this helps you out. This was a sticky problem. I wish there was a better solution, but when they fix the API I will stop playing with the database. And to those of you who would say that answering your own question in the third person is akward, I say "HA!"