well something strange that i notice is that in image 2 when you're extruding, the edges of the cube that are not involved seem to also have faces... which isn't right. not counting the new extruded part, you've got 9 faces showing on your cube(or at least 9 face selection handles), when there should only be 6 faces total in the whole cube... it makes me think that the reason there's extra verts is because it's extruding not only the 4 faces you think you're extruding, but also an additional 4 faces that should never have been there to begin with.

enhzflep's got the right solution, although i don't think i'd have my tolerance set so low... even a value like .05-.1 is usually sufficient without grabbing verts you don't want to be merged, but then again seeing how your cube is only 1X1X1 that's not a lot of space to move around anyway... so maybe a .01 would suffice for your case - but i think the important question would be, 'why are there so many faces on that poly object to begin with?'

edit: and after posting, i saw that ransid's (quicker?) post answered my question.