Here is a simple test if someone can confirm this. Create a note object. Number it "NOTE1". Rename it and change the note to "NOTE2". Go back and try to create a new note numbered "NOTE1". Reply back if you get a uniqueness error on creating the second note. Search for "NOTE1". You should find nothing.
What I noticed is that since notes are EPMDocuments but do not have a filename (aka CADNAME), they are created with a CADNAME that matches the number. Rename actions to change the number do not have a filename field hence CADNAME cannot be change. CADNAME must be unique so that is why you get the error. Reported bug to PTC. Tested this on 10.1.
