Muse supported Stereophonics a "couple" of times in the USA. Matthew Bellamy indicated that he found it pleasant to socialise with them between these gigs. Due to a misunderstanding between each band's agents, sometime during the Origin of Symmetry tour the Stereophonics made false claims about the band to the press, claiming that Muse had turned down a twenty thousand pound concert offer because they wanted more money. Booking agents apparently referenced these allegations when Muse were booking concerts.
Bellamy alleged that the Stereophonics asked for 1.7 million pounds to perform at the Carling Weekend, Reading and that they'd taken the Performing Rights Society money from a band that supported them.
Stereophonics also played the main stage at V Festival 2008, before Muse's headlining slot
There are no indications that either the Stereophonics or Muse are musically influenced by the other.