While, not exactly at the same time, he stole it as he ended his turn then the fireflyqueen card came, that's how I think it's happened. I actually noticed it in my own turn. When I saw the new card is fireflyqueen, and he have a firequeen as a permanent. It has to be mine, because when I move the mouse over it, it shows an unupgraded version, and my opponent's is upgraded.