Let me tell you what I used. I hooked up 2 30amp relays to my inverter positive from battery. One of them is switched by my ignition, the other switched by my computer. I found that with one relay, it wasn't enough juice passing thru, and my inverter would die if my subs hit a deep note. So I decided on 2 and haven't had a problem. I hope that will help you some.
As far as your relay problem, why don't you get a bigger relay? It's always better to have too much then not enough.