Yea -- the objects need to be a single object for you to merge vertices. Also -- you may want to drag-select over the vertice... it seems to me like Maya likes selecting the same vertice over and over if you just shift-click the same spot 2ce. Make sure that both are selected (in spite of not being able to visually tell... they occupy the same space)