Robert Palmatier, Food: A Dictionary of Literal and Nonliteral Terms (2000) has this useful discussion of the phrase:
HAVE A BONE TO PICK to have a bone to pick with someone. To have an argument to settle with someone. [Charles Funk,] H[eavens to] B[etsy and Other Curious Sayings (1955)]: mid-19th cent. Source: BONE. M[erriam-]W[ebster] C[ollegiate] D[ictionary, tenth edition (1994)]: O.E. As long as a single dog has a single bone to pick on, there is no problem. The dog takes its time, removes every scrap of meat (usu. beef), and then starts to gnaw on the bone itself. In the early-16th cent., this peaceful activity of the dog became a metaphor for a philosopher mulling over an idea or a preacher delivering a sermon. However, when a second dog was added to the picture, the bone became a prize to be contested, leading to a violent dog fight. Later in the 16th cent., the object that the dogs were fighting over became a metaphor, a bone of contention, for the subject of a human quarrel. For example, two neighbors might quarrel over a barking dog or an overhanging tree, neither of which is life-threatening. In the 19th cent., the senses of bone of contention and bone to pick were combined into the expression to have a bone (of contention) to pick with someone.
Thus, according to Palmatier, although (as user070221 notes in a comment above) "bone to pick" dates back to the sixteenth century, the full expression that the poster here asks about dates back only to the nineteenth century.
A Google Books search for "a bone to pick with" tends to corroborate this view, as the earliest match for the expression appears in a letter, dated March 21, 1811, and posted from Billingsgate, to the editor of The Christian Observer (May 1811):
I am a Skate, sir, living in hourly expectation of being crimped, and thus have all the pretensions of a dying martyr to be heard. But think not, sir, I mean to complain merely of my individual grievances. I wish to plead the cause of all our tribe. It is highly probable that some of the great public will soon pick my bones; but, in the mean time, I have a bone to pick with them.
Anther instance of the phrase appears again in a letter to the editor, this time to the editor of The Churchman, a Magazine in Defence of the Church and Constitution (December 1838):
Sir,—The Proprietor of the Review or Magazine which you edit has unquestionably performed a very great service to the Church; and I am convinced, from an impartial perusal of the controversy in which he has been placed, that he is a very deserving, but most injured man. To such different conclusions do real facts draw different men. However, I have a bone to pick with you. I am a stout Churchman, attached without one taint of heresy, without one particle of itching ears for new doctrines, to the long-established faith of my forefathers, who were taught to adore their God in the purity of holiness, and to venerate our Established Church, as the purest depository of God's doctrines on this earth.
After this, Google Books returns a flurry of matches from the years 1847–1850. The combined expression appears to have originated in Great Britain.
Samuel Fallows, The Progressive Dictionary of the English Language: A Supplementary Wordbook to All the Leading Dictionaries of the United States and Great Britain (1885) offers this brief entry for the term under a larger entry for bone:
To have a bone to pick with one, to have an unpleasant matter to settle with him. [Colloq.]
These particulars tend to confirm the argument that Palmatier makes that "to have a bone to pick with someone" emerged in the nineteenth century through a surprisingly late coalescence of two sixteenth-century English expressions: "to have a bone to pick" (in a thoughtful, philosophical way) and "a bone of contention" (to be worried over by competing intellectual mastiffs).