This one of several serious bugs with Maya's dynamic attributes and scripting. I ran into this myself when writing a UI for an attribute adding script.
Basically, what is happenning is that the AE isn't updating. If you query your attribute through script, you can see that the attribute has actually changed internally. If you use the resetAE command, Maya will rebuild the AE and your new enum values will show up.
But wait there may be more!
If you are doing this within a larger script, Maya may get VERY upset about updating the AE while it is doing other things. So upset that it may crash out on this command. The solution to this is to use evalDeferred(resetAE) . This tells Maya to update the AE as soon as it is not busy.
--JeffD