The linked video sounds fine to me. So it seems its only headphones that sound muddy? That could be a few things;
1-crappy headphones(you didn't mention brand or model)
2-crappy headphone amp(never used the Mackie, but am very happy with the ART HeadAmp 6 Pro)
3-high-impedance(600 ohm) headphones driven by an amp designed for low impedance(8-32 ohm) phones
4-clipped signal feeding the headphone amp
How are you feeding the headphone amp? Does it get the main mix or are you using sends? I would use sends and this would allow you to insert a master track for the send, and insert an EQ plugin to try an compensate(this is grasping at straws because I think something else is to blame)