Congratulations on your MAD Ear+ HD. This amp is good enough that it might be all the headphone amp you'll ever need, with the right cans and tube choices.
The tube that makes the most difference is the 12AX7 and its variants. Fortunately, you can find many good alternatives for that tube, although the NOS vintage tubes have become quite expensive. Most folks are searching for pairs, so single tubes are often less expensive. You can also try fussing with the 12B4A's but the upside potential seems small compared to what happens with the right ECC83's! Lloyd's choices there are pretty good. I'd recommend focusing on the input tube as the place to start (and end).
I find that the 5751 variants are often better-sounding than many 12AX7's, but they do have lower gain, i.e. they amplify less, require higher settings on the volume control for the same loudness. The "definitive" ratings of these tubes can be found in "Joe's Tube Lore" which also has driven up the prices of the NOS tubes that he rates highest. See http://www.audioasylum.com/scripts/d.pl?audio/faq/joes-tubes.html for example. Over the years, I have tried many of the tubes discussed and don't always agree, but in general this is a good starting point if you want to know more about what everyone is talking about.
Don't take it as gospel, nor as an indication of the best way to go for your amp. Sometime's it's just a matter of what you can find. The current production Gold Lion (Genelex brand) 12AX7's are a nice starting point, and should provide a nice upgrade over the stock tubes. These use the British designation ECC83 which are equivalent to 12AX7's. You might be happy to stop right there. Psvane 12AX7 tubes are also getting good reviews, but I have no personal experience with them.
I've tried various Mullard's and Amperex variants, and find the Mullards are often rich and creamy, but reticent in the treble, whereas the Amperex tubes tend to be more open-sounding and retain nice mid's. Finding good ones is a crap-shoot, especially on the big auction sites. I've had better luck through Audiogon, or the vintage tube $$ellers like Vintage Tube Services, Brent Jesse or TubeMonger, but the prices are much higher. On the plus side, these guys test the tubes and provide guarantees.
My current faves for the MAD amp are some GE 5-star triple-mica black plate tubes that I found cheap at a yard sale. Like $10 for 4 of them. Sylvania 5751's are also extremely nice. I did not care for the Telefunken 12AX7's I've tried (ribbed plate), nor the Siemens. I had some Mazda Cifte 12AX7's from Japan that were pretty nice, with a lively presentation that I keep coming back to.
My recommendation would be to spend some time with the stock tubes and get to know the sound well. Then try some other current production 5751 or 12AX7 tubes and see how much difference they make, and whether you like what they do in combination with the cans you use. Then, try a few cheaper NOS tubes. And your own opinion is all that matters, despite thse who worship Joe's Tube lore.
Also your choice will likely change depending on what headphones you use. WIth Grados, you might love Mullards. I like frame-grid Amperex 12AX7's when I want higher gain, and the GE 5751's when I have more sensitive cans that don't require the extra gain.
Find what makes you happy and enjoy the trip!
