99% chance you may have wired it wrong, or used the wrong relay..
Those type of 20/30a relays come in a couple configs.
If the pic you posted one that appears to have the 87 & 87A terminals, in which case, one is Normally Open, one Normally Closed. They both need to be on terimal "87" of your relay which is the NO contact.
Example:
http://www.electronicsnmore.com/images/960.gif
So only 1 light would come on if you used that type of relay and actually wired one to 87 & one to 87A.
Whatever light works find out what pole it goes to on that relay, and wire them together. Both lights combined are not going to overload the relay.
If none of this makes sens, stop by my work one and we'll have you fixed up in a jiffy.