Replacing an old 4 way toggle by leviton 4 way switch
Unlike most people, you correctly understood the importance of the black and brass screws with 4-way switches.   You also correctly understood that you can swap travelers.  

But just to confirm, make sure the 2 wires on the brass screws go into one cable or conduit, and the 2 wires on the black screws go into a different cable or conduit. 

So I assume your problem is that the switch is "up" when it used to be "down". There are two ways to solve that. 


Physically flip the switch over when installing it... OR
Pick one side (e.g. brass) and exchange the two travelers.