You're right with the Elvis title, seanbss, and "Milkcow Blues Boogie" also makes more sense.
See here (my comment of 11 June 2015) for more cover versions of "Milk Cow Blues": http://www.45cat.com/record/7n314
The Elvis Presley version is actually called, "Milkcow Blues Boogie" NOT "Milkcow Boogie Blues" as erroneously referenced by fixbutte...Ricky Nelson and Eddie Cochran also covered the song - Ricky in a style similar to Elvis' definitive rockabilly version and Eddie in more of a rock 'n' roll style.
Like with Robert Johnson, it is incredible how many made-up stories about Kokomo Arnold circulate. One of them can be disproved just by looking at the displayed record labels:
¤ In 1934, James Arnold would have more success with it, calling it “Old Original Kokomo Blues." It was so popular it became his signature tune, and he was known then as Kokomo Arnold. (see here)
¤ When slide guitar specialist James Arnold revamped this number as "Old Original Kokomo Blues" for Decca in 1934, little did he know that this would soon become his permanent handle -- Kokomo Arnold. (see AMG)
The record labels (which are the original "sunburst" Decca labels from 1934) however demonstrate that Arnold had chosen his alias (possibly inspired by Scrapper Blackwell's "Kokomo Blues" from 1928) before the record even came out. The contemporary Decca ad also supports this interpretation.
Something else, from AMG and repeated similarly in other sources, is fictitious as well: Arnold moved to Chicago in order to be near to where the action was as a bootlegger, but the repeal of the Volstead Act put him out of business, so he turned instead to music as a full-time vocation.
Although Arnold had a dubious past as a bootlegger in the Mississippi Delta, it is rather unlikely that he moved to Chicago in the early 1930s just for the purpose of bootlegging. Instead he seemed to have worked mostly in the steel-mills (like he had done before and did again after 1938) and to have not played professionally before 1934. Later he commented: "I never wanted to make records. The first time, they had to almost carry me into the studio by force. I've always wanted to live a simple life, far from the futile excitement of this world."
The YouTube video of the original version of "Milk Cow Blues" was still missing. Here it is (apparently two takes of it with a break around 3:10, I guess that the first one was the master used for the record):
James "Kokomo" Arnold (born February 15, 1901 in Lovejoy's Station, Georgia) had already made one record in 1930 for Victor in Memphis, under the name "Gitfiddle Jim" ("Paddlin' Blues" b/w "Rainy Night Blues", Victor 23268). That record was a speedy bottleneck showpiece but didn't sell, so Arnold moved to Chicago to work in the steel-mills.
Only four years later he would make recordings again, when Kansas Joe McCoy recommended him to Mayo Williams, the legendary head of the "race records" department of the new US Decca label. The first sides from his first Decca session in Chicago on September 10, 1934 were coupled on this record here which became the first substantial national blues hit record since 1930. Actually both sides were extremely successful and well-known in the black community.
Tellingly Robert Johnson, who was not anywhere near as successful as Arnold at the time, used the basic structure of "Milk Cow Blues" for his first record and only hit, "Terraplane Blues" (1937), and he made an obvious follow-up of "Milk Cow Blues" with his "Milkcow's Calf Blues". Less obviously, Johnson copied the melody of the "Old Original Kokomo Blues" with its "baby don't you want to go" chorus for his own "Sweet Home Chicago".
Moreover, "Milk Cow Blues" made the crossover to C&W music and a white audience via the swinging cover of Johnnie Lee Wills And His Boys in 1941 (Wills' brother Bob later turned it into "Brain Cloudy Blues"), from which Elvis Presley derived his rockabilly version, "Milkcow Boogie Blues", in 1954. "Milk Cow Blues" has become a kind of rock music standard, covered countless times over the last decades -- like the flipside, even though in its "Sweet Home Chicago" shape.