I don't see how this is a problem. Just because the media isn't the same doesn't necessitate that the outcome also has to be different. It's like saying just because the guy driving in his car down the street at 5mph and a kid walking down the street at 5mph won't reach the same end just because their methods of getting there were different.
I'm not following your analogy here, but I think I see what you're getting at. I think your argument is that just because there are two different physical states, that doesn't mean they can't realize the same mental state.
So, even though you and I are not identical physically (you're in physical state A and I'm in physical state B), we can still have an identical mental state M.
Recall, though, the definition of physicalism: brain states are identical to mental states. Logical notion is easy enough: BS = MS.
And your argument, if I'm understanding it correctly, is that two different brain states can produce identical mental states.
So let me see if I can do a little reductio on this.
MS : Mental State
BS : Brain State
P1 : my brain state before the brain transplant
P2 : my brain state after the brain transplant
M : a mental state realized by a given physical (brain) state
=: the logical operator for the identity relation
^: the logical operator 'and'
~: the logical operator 'not'
/: 'therefore'
1) MS = BS (this is physicalism)
2) P1 = M (an instantiation of 1)
3) P1 = M ^ P2 = M (this is your premise, that two nonidentical physical states can realize the same mental state)
4) P1 =/= P2 (just the claim that P1 and P2 are nonidentical)
5) P1 = P2 (follows from 3 and the transitivity of identity claims).
6) / ~(MS = BS) (follows from 4 and 5 - reductio)
Now I guess you could argue that the identity relation isn't transitive in this case for some reason or another. But that just seems ad hoc.
At the very least, physicalism certainly doesn't get us the claim that two physical states can realize an identical mental state. Thus, physicalism loses a lot of its motivation.