Instead of quickly releasing a new album to regain her lost momentum, the Massachusetts native seemed to disappear from the country scene for quite awhile.
Now she's back and better than ever, though, with her sophomore album just released, the high-energy, upbeat "I'm Alright," and its first single "Bye Bye" having just spent two weeks at number one on the country charts.
Recently, Messina discussed the new album and the reasons for her disappearance.
The interview almost didn't even happen, though, due to a disaster on the road. "Oh my God! We were in Sheboygan, Wisconsin. We were supposed to leave at 10 at night and get into Nashville at 8 the next morningAnd the bus, we went to start it, and it just clickedWe were like, 'Oh no.' So we sat up all night long. I think the last time I looked at the clock was like 3:30 and I was so tiredA couple hours later I heard it startbut you know what? It's par for the course. It's part of the job," she says with a good-natured laugh.
So where was Messina during the time between "You're Not in Kansas Anymore" and "Bye Bye"? "Well, it took a year and a half to make (the new album), and the major problem was finding songs that we felt were strong enough, songs that fit my personality. Since we already had a record out, there were expectations to meet, a certain style people expected us to have, and we needed to really hone in on that and really focus this album, whereas my first album is a little bit of everything because we didn't know which direction we needed to go into."
All of that down time must have been frightening for Messina, who saw several new country acts take the airwaves by storm while she was stuck in a rut trying to find the right songs.
"The Kinleys? Awesome! Love them! And yeah, I was like, 'I want to be on the radio with those guys!' And Lee Ann Womack came out. And just awesome talent! So yeah, I was a bit worried because there was such great new talent coming out."
After the incredible success of "Bye Bye," one might think Messina's fears would be alleviated.
"It's so funny," she says. "I still worry. Every song is a new song, and I know from past experience with 'Heads Carolina' doing wonderfully and 'You're Not in Kansas Anymore' doing great, and then all of a sudden we stalled with 'Make Something of It.' So I know that radio doesn't have to play every record you put out there, so there is a bit of concern with each record that goes out, and a great deal of appreciation when they do decide to play it."
Despite Messina's nervousness, anyone who listens to the new album can hear plenty of potential hit singles. Her music has the kind of edge to it that country radio and fans love.
"Rockin' country!" she calls it. "It's not pop, it's not AC, it's just real rockin' country music. It's real heavy on the guitars and real driven and uptempo. Even the ballads have almost a rock feel to them."
The rocking feel of most of her album makes one particular song stand out. "Even God Must Get the Blues" is a stark piano ballad about the tragedies of this world. The heartbreaking lyrics describe a man who's killed "for the shoes there on his feet" and a woman who hides her face so no one can see the signs of domestic abuse.
"I sort of put it in my live show after the Oklahoma City bombing. I just really always loved it. Golly, that song is just so powerful to me. It's something I just really felt when I sang itPeople started to write and call and say, 'We need this song. Can we have a tape of it?'...We put it on this album because the fans asked for it to be there."
Another fabulous song is "Lesson in Leavin'," a midtempo song with a great groove that's revved up with loud guitars. Some long-time country fans might remember the song as a number-one hit in 1980 for another redhead, Dottie West.
"Dottie West was somebody that I truly admired," Messina says. "She was just, man, she was such a fighterShe lost everything she had because her heart was too big. She gave and gave and gave and gave to everyone else, and when it came time to help herself, she didn't have anything left, emotionally, financially.
"When we cut 'Lesson in Leavin',' we didn't try and cut it like she did. I said, 'No way. Those are just too big of shoes for me to try to fill.' Actually, Tim McGraw had the total creativity on that song, and he made it into something that he said was a Jo Dee song."
How did Messina get McGraw to co-produce her album anyway? When Messina met McGraw in her producer Byron Gallimore's office, McGraw's first single, "What Room Was the Holiday In," had just been released. It didn't even chart.
"We're very, very much alike, very passionate about things and just love the fire out of the music. So we just clicked, became friends, hung out, and when I had a deal with RCA, Tim had said at one point, 'You have to promise you'll remember me when you make it big-time,' and I was like, 'Aw, no problem, man. This is going to be great.' And I lost my deal with RCA. Then, boom, 'Indian Outlaw' came out. 'Don't Take the Girl' was released. Golly. His career just took offand he kind of put in a good word for me over at CurbHe got me backstage at Fan Fair where I kind of snagged one of the record executives there at the label, and the rest is history."
Some have called Messina one of the hardest-working artists in country music, and given her jam-packed tour schedule through the end of the year, it's hard to argue that point. "Oh my gosh! We're slammed! And I love it," she says with obvious relish. "If I wasn't busy, I'd be bored."