What Could Have Been: Cigarettes and Valentines, the follow-up to Warning that was supposed to be a return to Green Day's old sound. They recorded the entire album in 2003, but the master tapes were stolen before they could release it. Instead of rerecording everything, they decided to write an entirely new album, which became American Idiot.
They've been playing some of the songs from the album on the 21st Century Breakdown tour. The title track was featured on the live album Awesome As Fuck. It sounds like it would be right at home on Kerplunk or Dookie.
When Tim Armstrong was forming Rancid he asked Billie Joe to audition for the band. Billie Joe said no, as Green Day already had a few albums under their belt and were on the verge of becoming huge.