The phrase means, as you said, 'a different thing.' According to this website:
There was, it seems, a custom by which the gentry on the Scottish border with England would hold a picnic by a river. The custom was described by Thomas Newte in his Tour of England and Scotland in 1785: “It is customary for the gentlemen who live near the Tweed to entertain their neighbours and friends with a Fete Champetre, which they call giving ‘a kettle of fish’. Tents or marquees are pitched near the flowery banks of the river ... a fire is kindled, and live salmon thrown into boiling kettles”.
The way the phrase became an idiom, however, is not clear. Visit that site to read more about possible explanations of the idiom.