Yeah, that sounds like them! They're definitely worth catching live if you can, as they put quite a lot of effort into their visual performance. Details of their current tour are here (http://www.piersadams.com/RPR/RedPriestRecordings/Tour.html) - the most workable date for you might be London on May 18th.