It's not a bug, you see. Rather a feature of the current system. The discarded cards are computed by comparing your hand before and after the card was played.
If the Tribute targets itself for discard, it does not discard itself, so that's why you see only one card discarded.
Now let me explain what happened when you played that Militia. The problem is that you discarded a card and you recieved the same card to that position. So when comparing the hands the system sees no difference. The newcard flag partially helps to fix this problem.
In the case that card was in you hand and it wasn't marked as "new" and you discard it and receive the same card, the system can tell, because the newcard flag is now set (and it wasn't set before).
But in the case the newcard flag was already set for this card, the system cannot see the difference.
Fortunately this case should be quite rare according to my probabilities study.
We keep this system, because it has very simple and elegant implementation. The hand difference computation is independant of card effect code.
This flaw cannot be fixed in this system, rather the system would have to be reworked.