David,

I suggest before you narrow down the meeting between Twain and
Nast to two days in 1867 based on Twain's memory ten years later
that you consider Twain's news story that appeared
in the _Territorial Enterprise_ on February 27, 1868 datelined
Washington, January 30, 1868. Twain writes:

"They treat us houseless strangers well in the East. Thomas Nast, the
clever artist of Harper's Weekly is exhibiting a collection of great
caricatures of national subjects in New York and wants me to do the
lecturing for his show. I would, if I hadn't so many irons in the fire. I
would like it right well for a change, but then changes are risky. I must
hunt around for a handsome Pacific coaster to take the berth - because I
suppose it is personal loveliness Nast is after."
(http://www.twainquotes.com/18680227t.html)

If you check the online Union Catalog of Letters to Clemens at:

http://bancroft.berkeley.edu/MTP/twcorr.html

you will see that Twain was back in New York in January of 1868
and could have met Nast then.  If you rely strictly on Twain's
memory without other supporting evidence, you may get thrown
off track from time to time.

Barb