Studio work for the album was put on hold in mid 2007 due to vocalist Chad Gray's and guitarist Greg Tribbett's touring commitments with Hellyeah. At the completion of the Hellyeah tour, Mudvayne reunited and began recording with producerDave Fortman, who also produced their previous full-length release, Lost and Found. Having completed the tracking of the drums and guitars, as well as the recording of the bass and vocals, the band announced that the mastering stages were scheduled for completion by October 1, 2008. During the recording phase, Fortman revealed to MTV the tentative title The New Game, adding that the band planned to release a second full-length record six months after its release.
A video previewing a possible album track was uploaded to Mudvayne's MySpace profile on July 16, 2008. A second video appeared on the profile on August 19 showing Gray tracking vocals. The second video was later made a feature on the band's official website. On September 16, 30-second previews of "Fish Out of Water," "A New Game" and "Do What You Do" were made available for streaming on the profile. The first single, "Do What You Do," first received airplay on September 23. Mudvayne also shot a video for "A New Game" and released a second single to radio, "Scarlet Letters," that was first broadcast on March 9, 2008.[clarification needed]
A bonus song, "Fish Out of Water," was made available for download to customers who pre-ordered The New Game on the iTunes Store, or through Best Buy, and the deluxe digital version of the album also included a digital copy of By the People, for the People. On October 28, 2008, "Have it Your Way" was released exclusively by Revolver magazine through its website.
Fortman said the album should please listeners, but also incorporate a distinct rock and roll sound unheard on previous Mudvayne records. "It's heavy and has great hooks, but it also has some moments that are a little more rock 'n' roll that are really cool. It's not anything drastic, but every now and then you'll catch a little hint of old school rock. Also, the tones are a little more earthy sounding and a little warmer than Lost and Found." Singer Chad Gray has stated the album is "not light years away from what we've done in the past, but it's not the same." The album's sound has been compared to Alice in Chains and Motörhead.
The album has received mixed reviews from critics, earning a 50% rating on Metacritic, with positive reviews coming from Billboard, which wrote "Some of the fierce headbanging that is Mudvayne's stock in trade can still be found in 'The Hate in Me,' 'We the People' and 'Dull Boy,' but the bulk of the record finds the group playing its New Game with hard-hitting exuberance." Another positive review came from the Boston Globe, which wrote, "Mudvayne used to be viewed as somewhat of a joke band with its costumes and makeup, but they're more out front and naked now, with markedly more genuine results."
James Christopher Monger of Allmusic gave the album a mixed review and wrote "The problem is, Mudvayne's own predilection for predictable loud/soft/loud set pieces, forgettable melodies, and over-reliance on words like "sorrow," "rage," "abused," "disease," "nightmares," and "beatings" keeps things from ever leaving the tarmac." Another mixed review appeared in Q, which said, "This fourth album finds them repeating the nifty trick of simplifying Tool's complex musical equations. Math metal for dummies, anyone?"Rolling Stone was also mixed in its response, writing, "Mudvayne write some decent guitar hooks (check the title track), but their imagination is parched, with most songs hewing to one formula: riff, whimper, shriek, repeat."
Negative reviews came from Sputnikmusic, who wrote that "The New Game signifies Mudvayne's transition from elite metal juggernaut to their inevitable fade into obscurity." The Los Angeles Times also panned the album, writing "The album's gooey, mid-tempo grind at best evokes System of a Down stripped of ambition and eccentricity, and might elicit sympathy with whatever culprit is running around that no-stoplight town."