H Bridge only working one way
Here is an existing h-Bridge circuit that I used in another working project. This one leverages a low-cost H-bridge IC, the Diode International ZXMHC3A01N8. Note the 22K bias resistors used in conjunction with the GPIOs.



This circuit is driven by a low-power MCU, similar to your Arduino. The firmware always sets the two GPIO outputs to opposite states to switch the relay in one direction for like 30 ms., then switches them both back to the same state.  Switching the relay to the other direction resets the relay in the opposite direction.

You need to actively apply current flow to BOTH sides of the H-bridge to reverse it.  In your original description, it sounds like you're just removing the 5 volts from one, assuming the other side will switch.  My experience is you want deterministic control on both sides of this h-bridge.

Also, depending upon your current requirements, you may be able to get away with a less expensive, much more compact H-bridge IC solution like mine.  Hope that helps.