Dave is right, but I suspect the resistor you need will be just as hard to find as the correct relay.
You would need a 105-Ohm resistor in series with each relay's coil if you use a typical automotive 12v relay such as a Tyco or Bosch. However, it needs to be a 2-Watt rated resistor -- the little jobbies you can buy at Radio Shack are only 1/4-Watt and will burn out, as you discovered.
Based on some recent experience which I have had shopping for resistors at Rat Shack
I can state that they do in fact usually have a decent selection of high wattage ceramic resistors in addition to the fractional wattage ones.