Probably right, Bob. Magpies were common in northern Europe, and scarce to absent on the Atlantic seaboard of North America. The crow replaced it in some of the songs.
The magpie was resident in North America, but west of the Rockies and to the northwest. Lewis and Clark ran across them and brought one back with them. Of the animals that returned with them, only the magpie and a prairie dog survived (Gee, this thread is made for digression).

The first two lines of the song sung by Walters are essentially the same as those in the rhyme by Holder, quoted above. Both probably from the same origin.