Problem is evident in both the code I've written and Apple's sample AddMusic code (http://developer.apple.com/iphone/library/samplecode/AddMusic/index.html runs on Device Only).
Once you open MPMediaPickerController when you click on an item it appears to be impossible to subsequently unselect it. It actually just gets added to the MPMediaItemCollection again (that's fine, I can filter the duplicates later).
It strikes me as odd that you're unable to deselect something after selecting it. I had previously thought the implementation was for the 'add' button to function almost as a checkbox with on and off.
Am I missing something in the docs explaining how to deselect in a MPMediaPickerController?