Colorado potato beetle diet
They ate other Solanaceae species.  This University of Florida info page gives an excellent overview of the species, including its hosts (emphasis mine):


  Potatoes are the preferred host for the Colorado potato beetle, but it may feed and survive on a number of other plants in the family Solanacae, including belladonna, common nightshade, eggplant, ground cherry, henbane, horse-nettle, pepper (rarely), tobacco, thorn apple, tomato, and its first recorded host plant: buffalo-bur.


The naming history is a bit weird — being neither originally from Colorado or associated with potatoes — but hey, that's science.