Early occurrences of 'ball up'
Although (as Kris notes in a separate answer) Christine Ammer, The American Heritage of Idioms, second edition (2013), dates the origin of the expression "ball up" in the relevant sense to the first half of the 1900s, J.E. Lighter, The Random House Historical Dictionary of American Slang (1994)—which declines to endorse a theory of the phrase's origin—finds several earlier instances:
ball up v. {semantic devel[opment] obscure} 1. Intrans[itive] to become confused or muddled. [Earliest cited references:] 1856 B.H. Hall College W[or]ds 19: Ball up. At Middlebury College, to fail a recitation or examination. 1900 D[ialect] N[otes] II 22: Ball-up, v.i. To become confused {reported from 66 different colleges}. ... 2. Trans[itive] to confuse or muddle badly esp. mentlly; to mix up; to entangle oneself (with).—esp. as a ppl. adj. balled up confused; (hence) mentally unbalanced. [Earliest examples:] 1884 in Lummis Letters 53: That knapsack balls me all up. 1885 "M. Twain," in Letters II 465: I heard a canvasser say, yesterday, that while delivering eleven books he took 7 new subscriptions. But we shall be in a hell of a fix if that goes on—it will "ball up" the binderies again. 1887 Harper's Mag[azine] (Sept.) 605: "You seem balled up about something." ... "Balled up!...I'm done for!" 1895 Gore Stu[dent] Slang 12: He tried to explain the problem but he got all balled up.
The instance recorded by Willard Gore in "Student Slang" is worth quoting at greater length. It appears in The Inlander: A Monthly Magazine by the Students of Michigan University (December 1895):
balled up. a. To be confused. To come to a standstill after making spasmodic and somewhat erratic efforts to continue—as a horse does when snow gathers in balls upon its hoofs. "He tried to explain the problem but he got all balled up."
The repetition of hoofs (instead of hooves) in Gore and in Ammer is one indication that Gore is Ammer's ultimate source for the "balled-up snow" theory of "balled up." It is also pretty clear, since Lighter cites Gore without accepting (or even mentioning) Gore's suggested allusive meaning of the term, that Lighter is not entirely convinced of the validity of the theory.
The earliest example cited in Lighter, is of ball up as an intransitive verb, from Benjamin Hall, A Collection of College Words and Customs, second edition (1856), where it is reported exclusively from Middlebury College in Vermont. (The term doesn't appear in the first edition of Hall, from 1851.) But 44 years later, as Lighter notes, Dialect Notes reports ball up as an intransitive verb from a multitude of colleges (Lighter says 66, but I count 64). The glossary in Dialect Notes—Eugene Babbitt, "College Words and Phrases" (1900)—also lists 36 colleges (Lighter says 40) where ball-up was then being used transitively. Here is Babbitt's entry for that form of the phrase:
ball-up, v. t. To confuse. The intransitive use is the original one. It probably comes from the "balling up" of a horse in soft, new fallen snow, when a snowball forms within each shoe, making the horse's footing insecure and his movements awkward. [List of colleges where the term is used omitted.]
A possible divide in UK and U.S. understanding of 'ball up' from the early 1920s
The final citation in Lighter for ball up as a transitive verb suggests that the relatively uncontroversial reputation of "balled up" in the United States in the early part of the twentieth century was not recognized in Britain:
1959 [Sidney] Bechet Treat It Gentle[: An Autobiography] 132 {ref[erring] to 1921}: "Your Honour, I'm all balled up." That is what I said ....But my God, you should have seen the judge. Later, it was explained to me; in England all balled up, that's a bad expression, it's a hell of a thing to say, you just don't use it.
Here is a fuller version of Bechet's description of his experience at a deportation hearing in a British court in 1921:
While I was there in that court, the judge was asking me all kinds of questions and I was trying to answer, but I didn't understand all it was they'd made it up to look like. What do I know about all these legal ways? Then at one point the judge, he told me, 'Why don't you explain yourself?' and I said, 'Your Honour, I'm all balled up.' That is what I said. All balled up. But my God, you should have seen the judge. Later, it was explained to me; in England all balled up, that's a bad expression, it's a hell of a thing to say, you just don't use it. Well, my lawyer he got to the judge and explained to him how in America, all balled up is just something confused, it's being like a ball of twine that's wound up around itself. He told him it was an expression anybody could use in America. But the judge, he'd heard it his own way, and he was remembering it his way.
Bechet's story raises the question of whether "balled up" existed in the UK in the 1920s with a different and more vulgar meaning than it had in the United States. Eric Partridge, A Dictionary of Slang and Unconventional English (1937) indicates that "balls" and "all balls" were indeed deemed quite offensive expressions in that era:
balls; all balls. Nonsense (— 1890). In Feb., 1929, it was held to be obscene; by 1931 it had [begun to be] permissible in print. Low coll[oquial]. For semantics, cf. ballocks, 2, and boloney (orig. U.S.), qq.v., also the U.S. nerts (as an interjection). ...
But Partridge's entry for "balls-up" suggests that even in England that term was not necessarily viewed as being on the same level as "balls!":
balls-up. To make a mess or a blunder of; to confuse inextricably; misunderstand wholly; do altogether wrongly: low: C.20. Cf. U.S. ball-up and (also for balls-up) the somewhat rare ball, to clog, gen. of a horse getting its feet clogged with balls of clay or snow.
Partridge seems to see an affinity between British balls-up and U.S. ball-up, even to the source in hoof-clogging snow (or clay), but he hints that the ultimate source for the British form may be different than for the U.S. form.
Conclusion
"balled up" seems to have originated in U.S. college slang from the 1850s. The origin of the word choice remains obscure, but any notion that it was related to ball in the sense of "testicle" seems not at all well supported by the early recorded examples of its usage, and by its continued growth in popularity in the United States primarily through college slang (at least until 1900). Whether the British term "balls-up" had the same source as its U.S. counterpart is open to question, but Eric Partridge, who took pains with his labels for identifying the users of particular words, characterizes "balls-up" as "Low" rather than as "Schools" or "University."