locals() does not give you a copy of the locals dictionary that you can modify and expect the values to affect the actual locals they were copied from.  This is documented:

http://docs.python.org/library/functions.html#locals

You would need to pass InteractiveInterpreter the "real" locals dict from the frame to make your code work, and it sounds like you've already done this.  However, I don't believe that this is going to work in the general case (eg: in the face of nested scopes), which is why locals() is not updatable. The use case for InteractiveInterpreter is implementing a python-command-line-like utility, and thus has no need to update the locals in the current function.

A doc note about this in InteractiveInterpreter along the lines of the one in the 'exec' docs is almost certainly appropriate, so I'll leave this open as a doc bug.