Woody's tragic death in 1999 appeared to be the end of Gov't Mule, but Haynes and Abts found a way to go on, adding keyboardist Chuck Leavell to the lineup and recording "The Deep End" with a host of great bassists and special guests.
Meanwhile, Haynes has rejoined the Allman Brothers at the same time as Phil Lesh has deputized him in the most musically successful of the post-Grateful Dead lineups, Phil & Friends. Haynes was in the midst of a Phil & Friends stand at the Beacon Theater in New York when we talked, the same day we learned that George Harrison had died.
It didn't seem possible that Woody could be replaced in Gov't Mule. His sound was too unique.
"The first thing that came to mind was Gov't Mule was finished," said Haynes, "we're not even gonna try to keep it together. Then eventually from talking to other people, some of the people we talked to -- the guys in the Allman Brothers, Phil, the guys in Blues Traveler, James Hatfield and Metallica -- people who had lost members, very important members but somehow managed to move on. It kind of made us realize that we weren't in quite as unique a situation as we felt like we were.
"The pain that we were feeling was our own and is unique but it's not as unique as we thought. We felt like we were the only people in the world that ever felt like this. Other bands have carried on after losing major members, in some cases to achieve bigger and better things.
"Things change and it's never gonna be the same so you just open a new chapter and try to move forward. Dave Schools had a lot of time off from Widespread Panic so he volunteered his services.
"That was very valuable, that kind of gave us a little of the incentive we needed, but the last thing we wanted to do was start auditioning bass players to try and find a permanent replacement for Woody, especially since the next thing we were probably gonna do was the record. And that's what led us to the whole process of recording with all the different bass players."
"The Deep End" features a different bassist on every track, including some of the biggest names in the business -- Jack Bruce, John Entwistle, Bootsy Collins, Larry Graham, Flea and Willie Weeks among others.
"Once Matt and I figured out that we were gonna try to keep it together, we definitely made the decision that it was no longer gonna be a trio, that we would include a fourth member from that point out, whether it was keyboards or another guitar or whether it changed from tour to tour or project to project, we didn't want to put the pressure on ourselves of trying to restructure the chemistry we had with Woody in the power trio format.
"We didn't want to be constantly comparing ourselves then to now, and we didn't want to put the pressure on us or the new bass player or the audience to be making those kind of comparisons. So it seemed a more organic notion to make it a four-piece and open a new chapter and allow some of the other influences to come in that were already trickling in anyway."
Haynes had already been playing with Phil & Friends at that point.
"I'd worked with Phil for over a year at that point, based around Gov't Mule's schedule," said Haynes. "Gov't Mule was 100 percent full time and if there was some stuff I could do with Phil during my downtime, then that was great.
"After Woody died, the first thing Matt and I did was cancel everything except the few weeks that we had with Ben Harper that we decided we could do acoustically as a duo because having seen Ben's live show and how important the acoustic aspect is to him and his live audience, we thought we could pull that off.
"Everything else we just canceled ... we don't know what we're gonna do. That freed both of our schedules up and that's why I was able to consider doing the stuff with Phil on a more full-time basis and the stuff with the Allman Brothers."
Haynes got a call from Gregg Allman, who told him how he felt after his brother Duane died just as the Allman Brothers were poised for mass success.
"He even made the comparison between Woody's death and Duane's death in the way that they both saw great things on the horizon for their bands but never got to see them come to fruition," said Haynes. "I told him that I still had dreams where Woody would come to me and he was still alive and he said, 'Well, you'll always have those.'"
For the time being Haynes has decided to keep playing in all three groups at the same time.
"Until it gets too complicated," he allowed. "So far everybody's working together, and it just means that I have very little free time, but if it gets too hectic at some point, then I have to start re-examining the whole thing. I've always liked going from one thing to another to another."
Celebrity Couples of 2014 [PHOTOS]