Next Gen News reports that Mega Man 2 (aka Rockman 2: Complete Works), the PSone enhanced port of the NES classic, will release on the service within the first week of February.
Next Gen News -- whose been pretty spot on with these reports in the past -- notes the game, among other titles, will go on sale February 1st, priced at $5.99 ($3.00 for PlayStation Plus members). Sony have yet to confirm these reports, but, seeing that Mega Man 1 made its debut on the service last week, it would be fitting for subsequent games in the series to bubble up our way over time.
UPDATE: Oh, silly me. Yes it is official: Mega Man 2 on February 1st.
Thanks for pointing that out, Josh!