my dad found the everything is new single yesterday in a dutch shop. He didn't buy it, because he didn't know if there were some non album tracks on it. But he did recall a Rolling Stones track. So it's quite obvious it was the new single.
Apparently, 10 copies of "Everything Is New" are already available at Ultradisc, a French seller (http://ultradisc.ifrance.com/ultradisc). You can also order a copy via GEMM.