A fine or pretty kettle of fish
As Peter Shor's comment beneath Ralph Richardson's answer indicates, "kettle of fish" has been used as a slang term for several centuries. The same definition of the term that he points to appears in Francis Grose, A Classical Dictionary of the Vulgar Tongue, second edition (1788):
KETTLE OF FISH. When a person has perplexed his affairs in general, or any particular business, he is said to have made a fine kettle of fish of it.
The earliest instance of the expression that a Google Books search finds is from "The Rival Masons: A Dialogue Between Mr. D———, Mr. H———, and a citizen of London," in The Political State of Great Britain (December 1738):
H. ... I doubt [that is, fear] we have but rouz'd a sleeping Lion : A stop-Thief has sometimes saved a House-breaker ; and many a Wench has sav'd her Reputation by crying Whore first : But the more this Matter is stirred, the more it stinks, and I doubt we have made a fine Kettle of Fish on't.
This pretend dialogue is unusual for the multitude of proverbs and idiomatic phrases that the two knavish masons pitch back and forth in this part of the dialogue—"a Fool's bolt is soon shot," "When Knaves fall out, Honest Men come by their Rights," "a Word to the Wise," "Penny wise and Pound foolish," "putting a Spoke in my Wheel"—but as testimony taken at a trial for adultery adjudicated on December 5, 1738, suggests, "a fine kettle of fish" may not yet have been broadly familiar to English people. From The Tryal of a Cause for Criminal Conversation: Between Theophilus Cibber, Gent. Plaintiff, and William Sloper, Esq; Defendant (1739):
Mrs Hayes. ... One Day after I gave warning [that the plaintiff's wife's maid must vacate the room she had rented for her mistress to use for assignations with the defendant], Mr Sloper was in a great Passion above Stairs at something, and Mrs Hopson [the maid] came to me, You have made a fine Kettle of Fish of it, says she. I did not know what she meant by her Kettle of Fish. What Fish do you mean? says I. Why there, says she, you have been talking of Matters, and he's stark mad at it above Stairs.
The expression also appears (a decade later) in Henry Fielding, The History of Tom Jones a Foundling (1749), in the course of a tirade by Mr. Western to Mr. Allworthy:
'There you have done a fine Piece of Work truly. You have brought up your Bastard [Tom Jones] to a fine Purpose ; not that I believe you have had any Hand in it neither, that is, as a Man may say, designedly ; but there is a fine Kettle of Fish made on't up at our House.'
In all of these instances, muddle seems to be a fair translation of the intended sense of "fine kettle of fish." In explaining the origin of the phrase, J.C.M.H., "Slang Terms and Their Derivations," in Bailey's Monthly Magazine of Sports and Pastimes (February 1872) argues that the kettle in question is not cookware:
We talk of a 'pretty kettle of fish,' and kettle is vulgarly supposed to refer to the culinary vessel in which fish is boiled ; this, however, is a mistake, as kettle is a kind of net in which fish is caught, and 'a pretty kettle of fish' merely means a bad catch.
Ebenezer Brewer, Errors of Speech and of Spelling, volume 1 (1877), endorses the same explanation, arguing that kettle is a corruption of kiddle ("a basket for catching fish"); in this, Brewer echoes the earlier suggestion of Anne Baker, Glossary of Northamptonshire (1854). A comment in Gentleman's Magazine (March 1823) begins its discussion of "kettle of fish" with the description of a Fête-champetre, as described in Newte's Tour (1785), cited in Mark's answer above, but then speculates in a different direction:
We much question, however, that it is an explanation at all, and for this reason: Fête-champetre would be doubtless a jovial affair;—how, then, does it happen that "kettle of fish" is a phrase never used but when something is spoilt or done amiss, thus: "you have made a pretty kettle of fish of it!" It is a question for the commentator on proverbial expressions, whether this application of "kettle of fish" to blunders or mismanagement arose from some miscooking of salmon at any of the Fêtes-champetres alluded to. The common expression "you have made a mess of it" evidently originates in some unfortunate overboiling.
A different kettle of fish
Since "another kettle of fish" and "a different kettle of fish" emerged as idioms more than a century after "a fine/pretty kettle of fish" did, the meaning of the new phrases was probably at least tinged with the notion that the metaphorical kettle of fish in question might be problematic. That is, "another kettle of fish" didn't simply mean "another thing altogether" but "another thing—and one that may be troublesome to put in order." This sense of the phrase is supported by its first Google Books appearance, in 1860. From Oliver Optic, Marrying a Beggar (1860):
"I had almost forgot to mention that brother Joseph had arrived in New York, and telegraphs that he shall be here to-night by the New Haven train."
"Just like you! Never tell of a thing till the last moment!" said the lady petulantly.
"I received the despatch only two hours ago."
"Here is another kettle of fish," continued the lady, musing. "That everlasting niece of yours is in the way again."
But very quickly the "another thing altogether" meaning seems to have taken over. From Harry Hooper, "Left on Board," in Under the Crown (February 1869):
"A southerly wind and a cloudy sky" may be a very pleasant theme for fox-hunting squires in dear Old England, but when a man is under a cloud in a foreign country, with a southerly wind in his pockets, and Mary Thompson's mark, " M. T." on his clothes chest, then it's quite another kettle of fish. This, however, was my sad case.
From "Parliamentary Jottings," in Touchstone: A Saturday Journal of Criticism, Commentary, and Satire (October 30, 1869):
The faithful minister, we are told, may always rely on adequate and generous support, and if at any time, ... he should be in a state of semi-starvation, he ought rather to like it than otherwise, especially if he has a wife and children. We must pay the policemen, the Judge and the gaoler, but those who do more than any other class of men in the community to diminish the need for either, must be deprived of the scanty pittance doled out to them of late years with such bad grace. But the legislator is altogether another kettle of fish. He is such an etherial being, that we must not force him to gain a living by contact with the harsh, coarse world.
And similarly with "a different kettle of fish." From Francesco Abati, See-Saw, volume 2 (1865):
"Well, of course you had a great advantage over me so far. ...There's nothing done here in a regular way, except a little gout and rheumatism. Accidents, of course, one can never depend upon, and what's the use of a case like this once in five years? There couldn't be a worse county than this. Now, when I was a young man practising in Smithfield, and taking in free patients, it was a very different kettle of fish. My goodness!” said the doctor, voluptuously smacking his lips, “ that was a neighbourhood. Something like disease there—and a nice variety of it, too! ..."
And from an 1868 translation of Goethe's Egmont:
Jetter. ... Have you heard one of these preachers?
Soest. First-rate fellows! A short time ago I heard one of them preaching in a field before thousands and thousands of people. A very different kettle of fish, I can tell you, to that which our pulpit droners give us, smothering the people with their scraps of Latin. My man spoke out as if he meant it.
Conclusions
To judge from Google Books results, "a fine/pretty kettle of fish" (meaning "a muddle") has been idiomatic in English since at least 1738, and "a different/another kettle of fish" (very quickly meaning simply "quite another thing") has been used since at least 1860. The latter expressions seem very likely to have emerge from the former ones, the shift in meaning appears to have be swift and substantial.