I agree that changing tubes can make quite a difference, however, I do not agree with your statement to "have the very best tubes that money can buy". This statement would suggest that the more expensive tube is better, which from my experiences is not true. Just as the most expensive cables and power cords are not necessarily the best. I would recommend trying different tubes if possible, and choose what sounds best to you, in your system. You'll be surprised that the tubes you choose will probably not be the most expensive ones.
I also would not say that changing tubes are the only way to go. I know some who find more satisfaction from changing cables, power cords, coupling caps, or even internal parts of an amp. Tubes are just one more variable to experiment with. You're lucky you only needed one pair, my amp (BAT) uses 3 pairs of 6SN7's, and has a reputation for being hard on NOS 6SN7's. I've found that a $100/pair of Sylvania JAN Black base 6SN7GT V231, circa mid 60's work pretty well for me.
For me the key is balance. I wouldn't use ultra expensive tubes with cheap cables/cords anymore than I would use ultra expensive cable/cords with cheap tubes.