I suspect your relays have built-in suppression diodes and, as such, the coil connections will be polarity sensitive - if these are connected incorrectly the internal diode will be forward-biased - pulling your power supply voltage down.
Compare the full part number of your relays (pay particular attention to the last few digits) with the information in the datasheet to confirm diodes (or not).