Wait...you tried merging vertices with the "V" key?

If so, that's not going to work :p

"V" is the shortcut for "snap to vertices." While you have one vertex selected, and the translate (move) manipulator active, hold down "V" and middle-mouse-drag/click near the vertex you want the one you have selected to snap TO.

This pretty much makes it so that the vertices are lying right on top of eachother; just open up the merge vertex, and the default of .0001 (or whatever) should work perfectly.

It helps if you have the poly count on, so that when you merge vertices, you can see that you do indeed have two vertexes selected before the merge, and one after you have merged.



In case you didn't know:

For Merge Vertices (in Maya 7):
Modeling Menu Set -> Edit Polygons -> Merge Vertices

To display the Poly Count (in Maya 7):
Any Menu Set -> Display -> Heads Up Display -> Poly Count



EDIT:

arran beat me by 3 minutes :p