2003-2004: Conturbações e Segundo Trabalho

Depois de longas férias, "Here It Comes Again", o primeiro single do segundo álbum solo de Melanie C, "Reason", é lançado em 24 de fevereiro de 2003, mas a música só conseguiu um #7 na parada inglesa. O segundo álbum solo, "Reason" é lançado em 10 de março e estréia no #5 na Inglaterra. Em abril Melanie começa sua turnê pelo Reino Unido e Irlanda.

No dia 2 de junho, o 2° single de "Reason", "On The Horizon" é lançado, embora a canção tenha obtido ótimas críticas músicais, os fãs reclamam que o single estava sofrendo problemas de distribuição pela Virgin Records, pois quando o single era encontrado em alguma loja, era em pouca quantidade, com isso o single fica em 14º lugar. Os rumores de que tanto Mel C quanto a gravadora Virgin não estavam bem, tomaram força.

"Melt" e "Yeh Yeh Yeh" foram selecionados para serem lançados como 3° e 4° singles em uma versão dupla. Depois de acordos entre a gravadora e Mel C, o single duplo foi finalmento lançado no dia 10 de novembro. E nos charts, as posições dos singles foram decepcionantes em comparação com a qualidade das músicas que foram elogiadas pela crítica, ficando em 27º na primeira semana de lançamento. O single tinha sido pouco divulgado, só com algumas apresentações de Mel na TV, já que a cantora tinha sofrido um acidente que deslocou sua perna no programa The Games da TV inglesa.

Com o fracasso do álbum, no dia 30 de dezembro de 2003, a saída de Melanie C da gravadora Virgin Records é oficialmente anunciada. Acreditam que Mel C e a Virgin Records chagaram a um acordo, pois Mel C não estava satisfeita com a falta de divulgação de seu último álbum e a gravadora com a suas vendagens, e ambos cancelaram o contrato que iria até 2006.