The solution was quite simple, this one doesn’t mess up the paths. However it feels like this method is slower.

$categoryId = 2269;
$parentId = 2268;

$category = Mage::getModel(‘catalog/category’)->load($categoryId);
$category->move($parentId, null);