But Hayden soon learned that his brand of country music was considered too country. The possible major label deal was dead in the water.
He made it back to Texas with his head hanging low for awhile. And when Hayden tried getting other labels interested in his recordings, there were no takers.
So, what is a 22-year-old to do? Put out a record on the fledgling label of his mentor, Robert Earl Keen, and Keen's wife, Kathleen, and let the strong, favorable reaction roll in.
Of course, when you entitle your album, "The Real Thing," you had better deliver on the promise.
But Hayden had little concern that his brand of country was the real deal in an age when his blend of honky tonk and traditional country sounds isn't burning up the radio airwaves. A more pop oriented brand is what's au courant.
"The Real Thing" actually is an old song penned by Chip Taylor of "Wild Thing" fame.
"We've been playing that song for quite awhile," says Hayden in a telephone interview on his birthday from his home in Pleasanton, Texas, about 30 miles south of San Antonio. "We knew it was going to be a kind of song that we were pushing at first to get airplay. It just went along with our idea of what we do - real country music. Also, it was kind of a set up to call the record 'The Real Thing' because it was kind of setting yourself up for something. (At) the same time, we wanted to let people know it was real country music. It was mine and Robert Earl Keen's (idea). We had figured that before we put the record out, we'd call it that."
"I wasn't too nervous about it because I wanted as many people as a we can to hear it. I'm real happy, proud of the way it turned out," he says.
Hayden included three other covers and co-wrote seven songs with Bill Whitbeck of Keen's band.
Perhaps the most poignant song is "December Rose," based on a true story. An old man who had lost his wife showed up at a Kerrville, Texas gig of Hayden in December 1998 and asked if he knew old songs. Hayden proceeded to play "Corinne Corinna" on request, the last song the man - whose name Hayden does not know - danced to with his wife.
The song brought a smile to the gentleman, and he gave Hayden a rose he had bought for his wife. Hayden now keeps it in his guitar case.
As for covers, Hayden also tackles Robbie Fulks' "Tears Only Run One Way," Billy Joe Shaver's "Black Rose" and Tom Waits' "I Hope That I Don't Fall in Love With You."
"It was the first song I learned how to play," says Hayden of "Black Rose." "I had the Billy Joe Shaver 'Old Five & Dimers' record. It was a real neat song. I'm not even sure if I understood it completely. We change it just a hair from the way Billy Joe Shaver and Waylon Jennings do it."
As for Waits, Hayden barely had any familiarity with him. "I'd heard the name and maybe one time I'd watched him on Austin City Limits or something. I didn't really know exactly any of his songs or anything like that. I wasn't really familiar with him. Kathleen gave me that record as well and thought I'd like it because I'm a big fan of Robert, and he's in that (vein)."
Hayden has the internet to thank for hooking up with the Keens.
He used to instant message Kathleen after finding her address on one of her husband's albums. "I think to get me to quit bugging her, she said to send her something."
Hayden sent a demo tape from his senior year of high school in 1997.
"Later, she told me she wasn't sure she had any intention of listening to it. She listened to it and really liked it. They came and saw me in San Antonio one night, and from there, they felt they could take over and manage."
Hayden said he picked up tips from Robert Earl Keen about songwriting and the process of putting on a show.
Hayden recorded a batch of songs, which were sent to different labels. One came across the desk of Tony Brown, then the head of MCA Records and a very powerful Nashville figure. He liked what he heard, caught a Hayden show at the Broken Spoke in Austin and invited Hayden to record in Nashville.
"It seemed like he was really behind it," Hayden says. "He took it to a committee at MCA. I guess the collective vote was that it was too country for what they were wanting to put out."
"It could have been a really neat deal, but at the same time now, I'm looking at it, I think I've matured and grown a lot musically in the last year and a half. Overall, it's probably a good thing. I felt like it was time. Now looking at it, I'm not sure I was completely ready for something like that to happen. It gave me a chance to work on what we're doing with our live show, and now we've got this record out on our own." (Three songs from the Brown sessions are on the CD)
"We had heard from some other labels we had talked with. The idea going around was that it was just too country for anybody it seemed like, which was frustrating. For me, it's a straight up traditional country record. That's pretty much all I can do. I didn't think it was all that far from Alan Jackson or somebody like that. It was a little frustrating. I'd rather be too country than not enough."
For now, it seems like Hayden has achieved a certain degree of success. After all, plans to go to Southwest Texas State University in San Marcos - the home of LBJ and George Strait - were put on hold. "The original deal with me and my dad (a middle school principal) is I'd give it two years, and we'd look at it at that point and see where it was at. Two years came and now four years. I guess we got past that."