"Korean Bodega" was released by Chrysalis Records on April 26, 1999, and was heavily promoted Garbage's remix, and the fact that Shirley Manson had contributed vocals to the remix. Released on two CD singles and cassette single, the Garbage remix featured on two of the formats, while the original album version on one. It charted at #15 on the UK Singles chart, the most successful single the band had released since "Scooby Snacks" three years earlier.
In the run up the release of Garbage's "You Look So Fine" single on May 24, Mushroom Records released promotional CDs to radio stations featuring both a radio edit of "You Look So Fine" and the reworked Fun Lovin' Criminals version. Much of the print ads for "Korean Bodega" pointed out that "You Look So Fine" and the Fun Lovin Criminals remix would be released the next month, and details of Garbage's single was sent out to fans on both artists mailing lists.