In September 2005, Clea collaborated with production group Da Playaz to release a single, named "We Don't Have To Take Our Clothes Off" a dance remake of the Narada Michael Walden song originally made famous by Jermaine Stewart. This single reached number 35 on the UK chart. "Lucky Like That", released in June 2006, was the band's fourth single. This single placed at number 55 on the UK chart. "Trinity", Clea's second album (but first UK album), was released on 3 July on Upside Records. Lynsey Brown left the band in November 2006. They then released the double a-side single "Stuck in the Middle"/"I Surrender" in Europe and toured Asia and Scandinavia in 2007. They also signed to EMI China and toured there on several occasions.