Just a quicknote – there is a glitch in the SharePoint OM, that if you update the choicelist for a profile property programmatically, without altering any other attributes of the profile property, the change is not accepted. To force acceptance of the change, you need to programmatically update another attribute of the profile property at the same time, such as the displayname (ensuring that its changed to a different value). What seems to be going on in behind the scenes is that an IsDirty flag is set when you try to update a profile property, however this is not set when you update the choice list. Note that it is also not set if you update the displayname to the same value as previous.
I would post example code, but i’m too tired! If anyone wants me to post example code, please post a comment below requesting this.