How to wire a 2 in 1 paddle switch
If they are on different breakers, you can't use a switch with a common hot.

You need something like (picked at random by Googling "dual independent switch") Decora 15 Amp Single Pole Dual Switch. The instructions include removing a tab that connects the hots if you need separate hots - just like using a dual receptacle on two separate circuits.

WAIT A MINUTE!!! From what you described, the old switch only had 3 wires! That means it also had 1 hot, 2 switched hot. In which case it was not on 2 separate breakers. If that's the case, you just have the wires confused. Separate the 3 wires. Determine which wire is hot using a tester (non-contact should be sufficient if it gives a clear indication, multimeter is the best test). Then turn the breaker (singular!) off again connect the hot to the common screw and one at a time connect one of the other wires to a switch and see what happens. You should be able to track it down that way to determine which wire goes where and get everything working.

Remember:


Screw location does not have anything to do with screw function. Each manufacturer, and each model within a manufacturer, can vary.
Color does not indicate function. It should, but often it does not. If things are wired (USA) according to code, you should find:


Green/bare = Ground
White/Gray = Neutral
Black/Red/other colors = Hot, Switched Hot, Travelers, etc.



So while typically black = hot, red = switched hot, there are no guarantees.