One thing has really nothing to with the other.
First case you're just changing the multiplier of by how much you want to amplify.
Second case you're changing an important physical part of the circuit.
Let's say you have two gain level:
Level 1: +6dB
Level 2: +12dB
If you're listening @80dB using the level 1, then when you switch to level 2 and lower the volume to equals the previous @80dB, sound should be EXACTLY the same. If it's not the same, the circuit was implemented wrong, simple as that.
But if you don't match both levels when comparing, of course level 2 will seems "better", because more volume will increase your perception of details and stuff.
Assume the amp has constant open loop gain at the two gain settings (which are probably closed loop gain settings).
This is a simple tube amp, it may have only one voltage gain stage, or maybe two or three, so it probably has low open loop gain, and hence low feedback.
Level 1: +6 dB of gain more feedback, hence less distortion and wider high f bandwidth
Level 2: +12 dB of gain less feedback, hence more distortion, and less high f bandwidth.
This could be why the two gain settings sound different.
Since I don't have schematic, I'm just guessing.
If it was an Op Amp based headphone amp and had a tremendous amount of Open Loop gain, then I would say you are more likely to be correct. But even a practical Op Amp doesn't have infinite Open Loop Gain and Infinite bandwidth. So it won't have infinite feedback, and therefore, always has some residual distortion.
As for the tubes, if you sub one 5654 for another they should sound the same, because they are both 5654 tubes.......right? Definitely maybe.
And if they ain't, what's the difference: gain parameters and parasitic capacitance, inductance. Louder or softer, more bandwidth or less bandwidth.