I did this 6 months ago, I do not have the code anymore, but I know you have to use the initFromSkeleton() method on your attribute set. You can search Magento's code for calls to this function, there are very few calls (just one perhaps). It will show you its usage.
EDIT: I remember I had the very same problem you are talking about, and I mailed about it. Here is the usage I was advised:
$attrSet = Mage::getModel('eav/entity_attribute_set');
$attrSet->setAttributeSetName('MyAttributeSet');
$attrSet->setEntityTypeId(4);//You can look into the db what '4' corresponds to, I think it is for products.
$attrSet->initFromSkeleton($attrSetId);
$attrSet->save();
The initialization is done before the save.