From Wikipedia:
“All Over Again” is a song written and originally recorded by Johnny Cash. He recorded it for his first single on Columbia Records.
The single (Columbia 4-41251, with “What Do I Care” on the opposite side) was released between September and November 1958.
“All Over Again” reached #38 on the Billboard Hot 100 and #4 on the Billboard country chart, while “What Do I Care” made it to #52 and #7, respectively. […
According to Mark Lewisohn in “The Complete Beatles Chronicle“, The Beatles performed “All Over Again” regularly between 1960 and 1962. However, no known recordings from that period exist.
