Im going by the simple idea that Disturbed plays to on average 5000 people a night, while Nevermore plays to approximately 1500 average, if they headline.
That is 3500 more people per night that will hear their music. Whether or not they buy the CD that night or two weeks later doesn't matter. Word of mouth is another big way to get exposure. I dont know how many records bands like Dark Tranquility have sold in comparison to Nevermore, but I know that with every record Nevermore has put out, it has sold better than the last one.
I think reinventing themselves would be the worst thing they could do at this point. They just got Steve Smyth as an official permanent member of the band and can work on making metal records with a dual guitar attack that will appeal to that segment of metal fans; the ones who like to hear fun and great guitar work with cool riffs and solos minus any major electronic effects and jump up and down metal.
I think the biggest problem the band has had, concerning exposure would be the inconsistencies they have had with their lineup, both live and on record. Tim Calvert, Pat O'Brien, Curran Murphy, Steve Smyth have all played with the band over the past years which has caused confusion on who is actually in the band. They have also concentrated on Europe rather than the USA much more when it comes to touring and press. In Fact, Nevermore are rather big in Europe, especially contries like Greece, Italy and other west European nations. Their UK fanbase is strong around London, but weak in the midlands....but then again, does anyone live in northern england anyway?
So, I think they're doing all right.