Bathroom light switch changed, now the light only turns on when the fan switch is turned on.
No, you didn't put the wires back the same.  You switched sides.   Or the new model of switch switched sides*. 

Put the old switch back on Just as it was.  Only this time, instead of looking at the physical position of the screws, look at the function of the screws.  One screw will be "common", the others switched.  Find those on the new switch.  

* The physical position of switch screws varies wildly from switch to switch.  I have never done a 3-way swap where the common and travelers were in the same place on the old vs new switch. There are only 12 possibilities, how can every single switch be different??