Following seven years away from the music industry, Andre re-appeared when he became a contestant on the ITV1 reality show I'm A Celebrity, Get Me Out Of Here! During his time in the competition, Andre penned the song "Insania", which was written about his time in the jungle. When the competition ended, East West Records offered Andre a record deal, which would see him release a new album before the end of 2004. It was revealed that East West had acquired the rights to Andre's hit "Mysterious Girl" some months before, following the collapse of Andre's ex-record label Mushroom Records. In February 2004, as an attempt to re-publicise Andre, East West penned a new remix of "Mysterious Girl", which was subtitled "2004", which was released on the 23rd as the album's first single. A week before the album's release, "Insania", the track penned by Andre during his time in the jungle, was released as the album's second single. The album was released on 7 June 2004, featuring both singles, ten new recordings and the original version of "Mysterious Girl". "The Right Way" was released as the album's third and final single on 7 December 2004. East West shipped over 60,000 copies and the album was certified Silver, though as of September 2009, it had only sold 15,069 copies.[2] Perhaps because of this, Andre was dropped from the label in early 2005.
